QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#513105#2191. Apprentice Learning Trajectorywhat_a_nameWA 1ms7800kbC++142.2kb2024-08-10 16:55:502024-08-10 16:55:50

Judging History

你现在查看的是最新测评结果

  • [2024-08-10 16:55:50]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7800kb
  • [2024-08-10 16:55:50]
  • 提交

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
                );
            }
        }
    }

    int res = 0;
    for(int i = 1; i <= cnt; ++i) {
        res = max(res,dp[cnt][0]);
        res = max(res,dp[cnt][1]);
    }
    cout << res;

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 7652kb

input:

2
5 7 1
1 9 2

output:

5

result:

ok 1 number(s): "5"

Test #2:

score: 0
Accepted
time: 1ms
memory: 7800kb

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: 7612kb

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: 7740kb

input:

1
314680159570 679536216645 149587989356

output:

0

result:

wrong answer 1st numbers differ - expected: '2', found: '0'