Submission #1239961
Source Code Expand
#include <cstdio> #include <iostream> #include <cmath> #include <cstring> #include <sstream> #include <algorithm> #include <cstdlib> #include <map> #include <queue> #include <utility> #include <vector> #include <set> #include <memory.h> #include <iomanip> #include <bitset> #include <list> #include <stack> #include <deque> using namespace std; #define mod 1000000007 int main() { int n; cin >> n; vector<pair<int, int> > v; priority_queue<pair<pair<int, int>, int> > qu; for(int i = 0; i < n; i++){ int a, b; cin >> a >> b; v.push_back(make_pair(a, b)); qu.push(make_pair(make_pair(a, b), i)); } pair<int, int> result[1000002]; // result[i].first : 時刻iから仕事を始めるとした時、 // 最も多く選ぶ方法において時刻iから始める仕事の番号 // result[i].second : 時刻iから仕事を始めるとした時、 // 最も多く選ぶ方法において時刻i以降で行う仕事の個数 result[1000001] = make_pair(-1, 0); for(int i = 1000000; i >= 0; i--){ result[i] = result[i + 1]; if(qu.empty()) continue; int a = ((qu.top()).first).first; int b = ((qu.top()).first).second; int num = (qu.top()).second; while(a == i){ // cout << a << " " << b << " " << num << endl; if(result[b].second + 1 > result[i].second || (result[b].second + 1 == result[i].second && num < result[i].first)){ result[i] = make_pair(num, result[b].second + 1); } qu.pop(); if(qu.empty()) break; a = ((qu.top()).first).first; b = ((qu.top()).first).second; num = (qu.top()).second; } } cout << result[0].second << endl; vector<int> ans; int num = result[0].first; int b = v[num].second; ans.push_back(num + 1); num = result[b].first; while(num != -1){ ans.push_back(num + 1); b = v[num].second; num = result[b].first; } for(int i = 0; i < ans.size(); i++){ cout << ans[i]; if(i == ans.size() - 1) cout << endl; else cout << " "; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - 仕事計画 |
User | maple |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 2016 Byte |
Status | AC |
Exec Time | 93 ms |
Memory | 11148 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample1.txt, sample2.txt, sample3.txt |
All | 0.txt, 1.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 2.txt, 20.txt, 21.txt, 22.txt, 23.txt, 3.txt, 4.txt, 5.txt, 6.txt, 7.txt, 8.txt, 9.txt, sample1.txt, sample2.txt, sample3.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
0.txt | AC | 5 ms | 8064 KB |
1.txt | AC | 5 ms | 8064 KB |
10.txt | AC | 5 ms | 8064 KB |
11.txt | AC | 5 ms | 8064 KB |
12.txt | AC | 6 ms | 8064 KB |
13.txt | AC | 6 ms | 8064 KB |
14.txt | AC | 6 ms | 8064 KB |
15.txt | AC | 6 ms | 8064 KB |
16.txt | AC | 6 ms | 8064 KB |
17.txt | AC | 6 ms | 8064 KB |
18.txt | AC | 59 ms | 10124 KB |
19.txt | AC | 64 ms | 10124 KB |
2.txt | AC | 5 ms | 8064 KB |
20.txt | AC | 82 ms | 10124 KB |
21.txt | AC | 57 ms | 10124 KB |
22.txt | AC | 66 ms | 10124 KB |
23.txt | AC | 93 ms | 11148 KB |
3.txt | AC | 5 ms | 8064 KB |
4.txt | AC | 5 ms | 8064 KB |
5.txt | AC | 5 ms | 8064 KB |
6.txt | AC | 5 ms | 8064 KB |
7.txt | AC | 5 ms | 8064 KB |
8.txt | AC | 5 ms | 8064 KB |
9.txt | AC | 5 ms | 8064 KB |
sample1.txt | AC | 5 ms | 8064 KB |
sample2.txt | AC | 5 ms | 8064 KB |
sample3.txt | AC | 5 ms | 8064 KB |