Submission #627119

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
627119	2022-08-12T08:20:04 Z	CodePlatina	Catfish Farm (IOI22_fish)	C++17	6 / 100	303 ms	24716 KB

fish

#include "fish.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<long long, long long>
#define plll pair<long long, pll>
#define tiii tuple<int, int, int>
#define tiiii tuple<int, int, int, int>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
#define DEBUG

using namespace std;

const long long INF = (long long)1e18 + 7;

struct SEG
{
    int N;
    long long ind[202020];
    long long qry(int l, int r)
    {
        long long ret = 0;
        for(int x = l + N, y = r + N; x != y; x >>= 1, y >>= 1)
        {
            if(x & 1) ret = max(ret, ind[x++]);
            if(y & 1) ret = max(ret, ind[--y]);
        }
        return ret;
    }
    void upd(int x, long long v)
    {
        x += N;
        ind[x] = max(ind[x], v);
        while(x >>= 1) ind[x] = max(ind[x << 1], ind[x << 1 | 1]);
    }
}dp[2];

long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W)
{
    vector<pii> A[N];
    for(int i = 0; i < M; ++i) A[X[i]].push_back({Y[i], W[i]});
    dp[0].N = dp[1].N = N + 1;
    for(int i = 0; i < N; ++i) sort(A[i].begin(), A[i].end());
    vector<pii> B[N];
    for(int i = 0; i < N; ++i) B[i] = A[i], reverse(B[i].begin(), B[i].end());

    for(int i = 1; i < N; ++i)
    {
        vector<pair<int, long long>> upd[2];
        long long ps = 0;
        for(auto [y, w] : A[i - 1])
        {
            ps = max(ps, dp[0].qry(0, y + 1)) + w;
            upd[0].push_back({y + 1, ps});
        }
        ps = 0;
        for(auto [y, w] : B[i])
        {
            ps = max(ps, dp[1].qry(y + 1, N + 1)) + w;
            upd[1].push_back({y, ps});
        }
        ps = 0;
        for(auto [y, w] : A[i])
        {
            ps += w;
            upd[0].push_back({y + 1, dp[1].qry(y + 1, N + 1) + ps});
        }
        upd[0].push_back({0, dp[1].qry(0, N + 1)});
        dp[1].upd(N, dp[0].qry(0, N + 1));
        for(auto [x, v] : upd[0]) dp[0].upd(x, v);
        for(auto [x, v] : upd[1]) dp[1].upd(x, v);

//        for(int i = 0; i <= N; ++i) cout << dp[0].qry(i, i + 1) << ' '; cout << endl;
//        for(int i = 0; i <= N; ++i) cout << dp[1].qry(i, i + 1) << ' '; cout << endl;
    }

    return max(dp[0].qry(0, N + 1), dp[1].qry(0, N + 1));
}

Subtask #1
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	65 ms	10560 KB	Output is correct
2	Correct	72 ms	12208 KB	Output is correct
3	Correct	19 ms	5076 KB	Output is correct
4	Correct	19 ms	5076 KB	Output is correct
5	Correct	216 ms	24716 KB	Output is correct
6	Incorrect	303 ms	22136 KB	1st lines differ - on the 1st token, expected: '300000000000000', found: '299997000000000'
7	Halted	0 ms	0 KB	-

Subtask #2
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	126 ms	17704 KB	Output is correct
3	Correct	132 ms	20784 KB	Output is correct
4	Correct	53 ms	10532 KB	Output is correct
5	Correct	71 ms	12212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	18 ms	5080 KB	Output is correct
11	Correct	18 ms	5088 KB	Output is correct
12	Correct	69 ms	13880 KB	Output is correct
13	Correct	90 ms	15624 KB	Output is correct
14	Correct	64 ms	11900 KB	Output is correct
15	Correct	73 ms	12384 KB	Output is correct
16	Correct	62 ms	11872 KB	Output is correct
17	Correct	73 ms	13112 KB	Output is correct

Subtask #3
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	5076 KB	Output is correct
2	Correct	18 ms	5068 KB	Output is correct
3	Incorrect	67 ms	9220 KB	1st lines differ - on the 1st token, expected: '21261825233649', found: '18478420432301'
4	Halted	0 ms	0 KB	-

Subtask #4
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 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	1 ms	212 KB	Output is correct
9	Incorrect	1 ms	340 KB	1st lines differ - on the 1st token, expected: '216624184325', found: '177984379387'
10	Halted	0 ms	0 KB	-

Subtask #5
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 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	1 ms	212 KB	Output is correct
9	Incorrect	1 ms	340 KB	1st lines differ - on the 1st token, expected: '216624184325', found: '177984379387'
10	Halted	0 ms	0 KB	-

Subtask #6
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 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	1 ms	212 KB	Output is correct
9	Incorrect	1 ms	340 KB	1st lines differ - on the 1st token, expected: '216624184325', found: '177984379387'
10	Halted	0 ms	0 KB	-

Subtask #7
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	5076 KB	Output is correct
2	Correct	18 ms	5068 KB	Output is correct
3	Incorrect	67 ms	9220 KB	1st lines differ - on the 1st token, expected: '21261825233649', found: '18478420432301'
4	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	65 ms	10560 KB	Output is correct
2	Correct	72 ms	12208 KB	Output is correct
3	Correct	19 ms	5076 KB	Output is correct
4	Correct	19 ms	5076 KB	Output is correct
5	Correct	216 ms	24716 KB	Output is correct
6	Incorrect	303 ms	22136 KB	1st lines differ - on the 1st token, expected: '300000000000000', found: '299997000000000'
7	Halted	0 ms	0 KB	-

Submission #627119

Compilation message