QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#513094 | #2191. Apprentice Learning Trajectory | what_a_name | WA | 1ms | 7788kb | C++14 | 2.2kb | 2024-08-10 16:53:23 | 2024-08-10 16:53:23 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define N 400010
#define PII pair<int,int>
#define PIP pair<int,PII>
PIP dashi[N];
PII times[N];
int cnt = 0;
int n;
int dp[N][2];
int t[N];
priority_queue<PII,vector<PII>,greater<>> q;
// bool cmp(PIP a,PIP b) {
// if(a.second == b.second) return a.first < b.first;
// return a.second < b.second;
// }
bool cmp(PII a,PII b) {
if(a.first == b.first) {
return (a.second & 1) < (b.second & 1);
}
return a.first < b.first;
}
signed main() {
cin.tie(0) -> sync_with_stdio(0);
cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> dashi[i].second.first >> dashi[i].second.second >> dashi[i].first;
--dashi[i].second.second;
times[i * 2 - 1].first = dashi[i].second.first;
times[i * 2].first = dashi[i].second.second;
times[i * 2 - 1].second = i * 2;
times[i * 2].second = i * 2 + 1;
}
sort(times + 1,times + 1 + n * 2,cmp);
for(int i = 1; i <= 2 * n; ++i) {
if(times[i].first != times[i - 1].first) {
++cnt;
t[cnt] = times[i].first;
}
if(times[i].second & 1) {
dashi[times[i].second >> 1].second.second = cnt;
}else {
dashi[times[i].second >> 1].second.first = cnt;
}
}
for(int i = 2; i <= cnt; ++i) {
for(int x = 1; x <= n; ++x) {
if(dashi[x].second.second < i) continue;
for(int j = 1;j < i; ++j) {
if(dashi[x].second.first > j) continue;
dp[i][0] = max( dp[i][0],
dp[j][0] + (t[i] - t[j]) / dashi[x].first
); // 这一秒不用
dp[i][0] = max(dp[i][0],
dp[j][1] + (t[i] - t[j] - 1) / dashi[x].first
);
dp[i][1] = max(dp[i][1],
dp[j][1] + (t[i] - t[j]) / dashi[x].first
);
dp[i][1] = max(dp[i][1],
dp[j][0] + (t[i] - t[j] + 1) / dashi[x].first
);
}
}
}
// for(int i = 1; i <= cnt; ++i) {
// cout << dp[i][0] << " " << dp[i][1] << '\n';
// }
cout << max(dp[cnt][0],dp[cnt][1]);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7648kb
input:
2 5 7 1 1 9 2
output:
5
result:
ok 1 number(s): "5"
Test #2:
score: 0
Accepted
time: 1ms
memory: 7720kb
input:
3 1 10 4 6 12 3 9 13 2
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 1ms
memory: 7788kb
input:
3 1 13 4 6 11 2 9 13 3
output:
4
result:
ok 1 number(s): "4"
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 7612kb
input:
1 314680159570 679536216645 149587989356
output:
0
result:
wrong answer 1st numbers differ - expected: '2', found: '0'