답안 #639562

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
639562	2022-09-10T15:51:13 Z	SlavicG	메기 농장 (IOI22_fish)	C++17	52 / 100	771 ms	2097152 KB

fish

#include "fish.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;

const ll inf = 1e16;
long long max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
    vector<vector<ll>> p(n, vector<ll>(n, 0));
    vector<int> len[n];
    for(int i = 0; i < m; ++i) {
        p[x[i]][y[i]] += w[i];
        len[x[i]].push_back(y[i]);
    }
    for(int i = 0; i < n; ++i) {
        for(int j = 1; j < n; ++j) {
            p[i][j] += p[i][j - 1];
        }
    }
    for(int i = 0; i < n; ++i) {
        len[i].push_back(n);
        len[i].push_back(0);
        sort(len[i].begin(), len[i].end());
        len[i].erase(unique(len[i].begin(), len[i].end()), len[i].end());
    }
    map<ll, ll> dp[n + 1][2];
    for(int i = 0; i <= n; ++i) {
        dp[0][0][i] = dp[0][1][i] = 0;
    }

    //0 - increasing, 1 - decreasing
    for(int i = 1; i < n; ++i) {
        vector<pair<ll, ll>> mx0, mx1;
        for(ll lastlen: len[i - 1]) {
            dp[i][0][0] = max({dp[i][0][0], dp[i - 1][0][lastlen], dp[i - 1][1][lastlen]});
            dp[i][1][0] = max({dp[i][1][0], dp[i - 1][0][lastlen], dp[i - 1][1][lastlen]});

            ll cur = 0;
            if(!mx0.empty()) cur = mx0.back().second;
            cur = max(cur, dp[i - 1][0][lastlen] - (lastlen ? p[i - 1][lastlen - 1] : 0));
            mx0.push_back({lastlen, cur});
        }

        reverse(len[i - 1].begin(), len[i - 1].end());

        for(ll lastlen: len[i - 1]) {
            ll cur = 0;
            if(!mx1.empty()) cur = mx1.back().second;
            cur = max(cur, dp[i - 1][0][lastlen] + (lastlen ? p[i][lastlen - 1] : 0));
            cur = max(cur, dp[i - 1][1][lastlen] + (lastlen ? p[i][lastlen - 1] : 0));
            mx1.push_back({lastlen, cur});
        }
        reverse(mx1.begin(), mx1.end());
        for(ll curlen: len[i]) {
            auto it1 = upper_bound(mx0.begin(), mx0.end(), make_pair(curlen, LLONG_MAX));
            assert(it1 != mx0.begin()); --it1;
            auto it2 = lower_bound(mx1.begin(), mx1.end(), make_pair(curlen, LLONG_MIN));
            assert(it2 != mx1.end());

            dp[i][0][curlen] = max(dp[i][0][curlen], (curlen ? p[i - 1][curlen - 1] : 0) + it1->second);
            dp[i][1][curlen] = max(dp[i][1][curlen], it2->second - (curlen ? p[i][curlen - 1] : 0));
        }
    }
    ll ans = 0;
    for(int i = 0; i <= n; ++i) {
        ans = max({ans, dp[n - 1][0][i], dp[n - 1][1][i]});
    }
    return ans;
}
/*
5 4
0 2 5
1 1 2
4 4 1
3 3 3
*/

Subtask #1
0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	713 ms	2097152 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Runtime error	771 ms	2097152 KB	Execution killed with signal 9
3	Halted	0 ms	0 KB	-

Subtask #3
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	734 ms	2097152 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #4
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	596 KB	Output is correct
10	Correct	3 ms	1492 KB	Output is correct
11	Correct	1 ms	596 KB	Output is correct
12	Correct	2 ms	1364 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	2 ms	1236 KB	Output is correct

Subtask #5
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	596 KB	Output is correct
10	Correct	3 ms	1492 KB	Output is correct
11	Correct	1 ms	596 KB	Output is correct
12	Correct	2 ms	1364 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	2 ms	1236 KB	Output is correct
15	Correct	2 ms	1236 KB	Output is correct
16	Correct	2 ms	596 KB	Output is correct
17	Correct	41 ms	8108 KB	Output is correct
18	Correct	40 ms	8128 KB	Output is correct
19	Correct	37 ms	8040 KB	Output is correct
20	Correct	37 ms	8052 KB	Output is correct
21	Correct	37 ms	8096 KB	Output is correct
22	Correct	81 ms	14992 KB	Output is correct
23	Correct	8 ms	2516 KB	Output is correct
24	Correct	26 ms	5708 KB	Output is correct
25	Correct	2 ms	1340 KB	Output is correct
26	Correct	7 ms	2488 KB	Output is correct

Subtask #6
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	596 KB	Output is correct
10	Correct	3 ms	1492 KB	Output is correct
11	Correct	1 ms	596 KB	Output is correct
12	Correct	2 ms	1364 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	2 ms	1236 KB	Output is correct
15	Correct	2 ms	1236 KB	Output is correct
16	Correct	2 ms	596 KB	Output is correct
17	Correct	41 ms	8108 KB	Output is correct
18	Correct	40 ms	8128 KB	Output is correct
19	Correct	37 ms	8040 KB	Output is correct
20	Correct	37 ms	8052 KB	Output is correct
21	Correct	37 ms	8096 KB	Output is correct
22	Correct	81 ms	14992 KB	Output is correct
23	Correct	8 ms	2516 KB	Output is correct
24	Correct	26 ms	5708 KB	Output is correct
25	Correct	2 ms	1340 KB	Output is correct
26	Correct	7 ms	2488 KB	Output is correct
27	Correct	57 ms	73220 KB	Output is correct
28	Correct	216 ms	42296 KB	Output is correct
29	Correct	406 ms	124560 KB	Output is correct
30	Correct	312 ms	124284 KB	Output is correct
31	Correct	312 ms	124488 KB	Output is correct
32	Correct	288 ms	54416 KB	Output is correct
33	Correct	318 ms	124376 KB	Output is correct
34	Correct	313 ms	123864 KB	Output is correct
35	Correct	142 ms	91932 KB	Output is correct
36	Correct	335 ms	122728 KB	Output is correct

Subtask #7
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	734 ms	2097152 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	713 ms	2097152 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

답안 #639562

Compilation message