답안 #832225

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
832225	2023-08-21T07:08:41 Z	fatemetmhr	메기 농장 (IOI22_fish)	C++17	9 / 100	158 ms	59900 KB

fish

// komak!

#include "fish.h"
#include <bits/stdc++.h>

using namespace std;

#define debug(x) cerr << "(" << (#x) << "): " << (x) << endl;
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define mp       make_pair
#define pb       push_back

typedef long long ll;

const ll mod   = 1e9 + 7;
const int maxn5 = 3e5 + 10;

vector <pair<int, ll>> av[maxn5];
vector <ll> ps[maxn5], dp[maxn5][2];

long long max_weights(int n, int m, std::vector<int> x, std::vector<int> y,
                      std::vector<int> w) {

    for(int i = 0; i < m; i++){
        av[x[i]].pb({y[i], w[i]});
    }
    for(int i = 0; i < n; i++){
        av[i].pb({n, 0});
        sort(all(av[i]));
        ps[i].resize(int(av[i].size()));
        ps[i][0] = av[i][0].se;
        for(int j = 1; j < int(av[i].size()); j++){
            ps[i][j] = ps[i][j - 1] + av[i][j].se;
        }
        dp[i][0].resize(int(av[i].size()));
        dp[i][1].resize(int(av[i].size()));
    }

    ll ans = 0;

    for(int i = 0; i < int(av[0].size()); i++){
        dp[0][0][i] = (i ? -ps[0][i - 1] : 0);
        int pt = upper_bound(all(av[1]), mp(av[0][i].fi - 1, mod)) - av[1].begin() - 1;
        dp[0][1][i] = (pt >= 0 ? ps[1][pt] : 0);
        if(i)
            dp[0][0][i] = max(dp[0][0][i - 1], dp[0][0][i]);
    }

    for(int i = int(av[0].size()) - 2; i >= 0; i--)
        dp[0][1][i] = max(dp[0][1][i], dp[0][1][i + 1]);


    for(int i = 1; i < n; i++){
        ll keepmx = ans;
        for(int j = 0; j < int(av[i].size()); j++){
            int pt = upper_bound(all(av[i - 1]), mp(av[i][j].fi - 1, mod)) - av[i - 1].begin() - 1;
            dp[i][0][j] = keepmx;
            if(pt >= 0)
                dp[i][0][j] = max(dp[i][0][j], dp[i - 1][0][pt] + ps[i - 1][pt]);
            ans = max(ans, dp[i][0][j]);
            dp[i][0][j] += (j ? -ps[i][j - 1] : 0);
            if(j)
                dp[i][0][j] = max(dp[i][0][j - 1], dp[i][0][j]);
            dp[i][1][j] = keepmx;
            pt = upper_bound(all(av[i - 1]), mp(av[i][j].fi, mod)) - av[i - 1].begin();
            if(pt < int(av[i - 1].size()))
                dp[i][1][j] = max(dp[i][1][j], dp[i - 1][1][pt] - (j ? ps[i][j - 1] : 0));
            ans = max(ans, dp[i][1][j]);
            if(i < n - 1){
                pt = upper_bound(all(av[i + 1]), mp(av[i][j].fi - 1, mod)) - av[i + 1].begin() - 1;
                dp[i][1][j] = (pt >= 0 ? ps[i + 1][pt] : 0);
            }
        }
        for(int j = int(av[i].size()) - 2; j >= 0; j--)
            dp[i][1][j] = max(dp[i][1][j], dp[i][1][j + 1]);
    }

    return ans;
}

Subtask #1
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	55 ms	44732 KB	Output is correct
2	Correct	68 ms	47268 KB	Output is correct
3	Correct	31 ms	40896 KB	Output is correct
4	Correct	31 ms	40916 KB	Output is correct
5	Correct	135 ms	59728 KB	Output is correct
6	Correct	158 ms	59900 KB	Output is correct

Subtask #2
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	28472 KB	Output is correct
2	Correct	95 ms	49876 KB	Output is correct
3	Correct	113 ms	53472 KB	Output is correct
4	Correct	58 ms	44776 KB	Output is correct
5	Correct	67 ms	47168 KB	Output is correct
6	Correct	13 ms	28372 KB	Output is correct
7	Correct	13 ms	28372 KB	Output is correct
8	Correct	13 ms	28392 KB	Output is correct
9	Correct	13 ms	28372 KB	Output is correct
10	Correct	31 ms	40912 KB	Output is correct
11	Correct	33 ms	40988 KB	Output is correct
12	Correct	63 ms	44780 KB	Output is correct
13	Correct	68 ms	47184 KB	Output is correct
14	Correct	58 ms	44796 KB	Output is correct
15	Correct	68 ms	46564 KB	Output is correct
16	Correct	68 ms	44776 KB	Output is correct
17	Correct	66 ms	46536 KB	Output is correct

Subtask #3
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	32 ms	40916 KB	Output is correct
2	Correct	34 ms	40984 KB	Output is correct
3	Incorrect	48 ms	41784 KB	1st lines differ - on the 1st token, expected: '21261825233649', found: '16359132159422'
4	Halted	0 ms	0 KB	-

Subtask #4
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	28372 KB	Output is correct
2	Correct	13 ms	28372 KB	Output is correct
3	Correct	13 ms	28480 KB	Output is correct
4	Correct	12 ms	28460 KB	Output is correct
5	Correct	12 ms	28372 KB	Output is correct
6	Correct	12 ms	28468 KB	Output is correct
7	Correct	12 ms	28372 KB	Output is correct
8	Incorrect	12 ms	28372 KB	1st lines differ - on the 1st token, expected: '2', found: '1'
9	Halted	0 ms	0 KB	-

Subtask #5
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	28372 KB	Output is correct
2	Correct	13 ms	28372 KB	Output is correct
3	Correct	13 ms	28480 KB	Output is correct
4	Correct	12 ms	28460 KB	Output is correct
5	Correct	12 ms	28372 KB	Output is correct
6	Correct	12 ms	28468 KB	Output is correct
7	Correct	12 ms	28372 KB	Output is correct
8	Incorrect	12 ms	28372 KB	1st lines differ - on the 1st token, expected: '2', found: '1'
9	Halted	0 ms	0 KB	-

Subtask #6
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	28372 KB	Output is correct
2	Correct	13 ms	28372 KB	Output is correct
3	Correct	13 ms	28480 KB	Output is correct
4	Correct	12 ms	28460 KB	Output is correct
5	Correct	12 ms	28372 KB	Output is correct
6	Correct	12 ms	28468 KB	Output is correct
7	Correct	12 ms	28372 KB	Output is correct
8	Incorrect	12 ms	28372 KB	1st lines differ - on the 1st token, expected: '2', found: '1'
9	Halted	0 ms	0 KB	-

Subtask #7
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	32 ms	40916 KB	Output is correct
2	Correct	34 ms	40984 KB	Output is correct
3	Incorrect	48 ms	41784 KB	1st lines differ - on the 1st token, expected: '21261825233649', found: '16359132159422'
4	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	55 ms	44732 KB	Output is correct
2	Correct	68 ms	47268 KB	Output is correct
3	Correct	31 ms	40896 KB	Output is correct
4	Correct	31 ms	40916 KB	Output is correct
5	Correct	135 ms	59728 KB	Output is correct
6	Correct	158 ms	59900 KB	Output is correct
7	Correct	12 ms	28472 KB	Output is correct
8	Correct	95 ms	49876 KB	Output is correct
9	Correct	113 ms	53472 KB	Output is correct
10	Correct	58 ms	44776 KB	Output is correct
11	Correct	67 ms	47168 KB	Output is correct
12	Correct	13 ms	28372 KB	Output is correct
13	Correct	13 ms	28372 KB	Output is correct
14	Correct	13 ms	28392 KB	Output is correct
15	Correct	13 ms	28372 KB	Output is correct
16	Correct	31 ms	40912 KB	Output is correct
17	Correct	33 ms	40988 KB	Output is correct
18	Correct	63 ms	44780 KB	Output is correct
19	Correct	68 ms	47184 KB	Output is correct
20	Correct	58 ms	44796 KB	Output is correct
21	Correct	68 ms	46564 KB	Output is correct
22	Correct	68 ms	44776 KB	Output is correct
23	Correct	66 ms	46536 KB	Output is correct
24	Correct	32 ms	40916 KB	Output is correct
25	Correct	34 ms	40984 KB	Output is correct
26	Incorrect	48 ms	41784 KB	1st lines differ - on the 1st token, expected: '21261825233649', found: '16359132159422'
27	Halted	0 ms	0 KB	-

답안 #832225

Compilation message