답안 #667029

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
667029	2022-11-30T08:02:57 Z	tatyam	메기 농장 (IOI22_fish)	C++17	9 / 100	222 ms	20676 KB

fish

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void chmax(ll& a, ll b){ if(a < b) a = b; }

// range chmax・1 点取得 で O(M log N)
struct SegTree {
    ll n;
    vector<ll> seg;
    SegTree(ll n): n(n), seg(n * 2) {}
    void range_chmax(ll l, ll r, ll x) {
        l += n;
        r += n;
        while(l < r){
            if(l & 1) chmax(seg[l++], x);
            if(r & 1) chmax(seg[--r], x);
            l >>= 1; r >>= 1;
        }
    }
    ll operator[](ll i) const {
        i += n;
        ll x = 0;
        do chmax(x, seg[i]); while(i >>= 1);
        return x;
    }
};
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    vector fish(N, vector<pair<ll, ll>>{});
    for (ll i = 0; i < M; i++) {
        fish[X[i]].emplace_back(Y[i], W[i]);
    }
    for (auto& v : fish) sort(v.begin(), v.end());
    SegTree up(N + 1), down(N + 1);
    ll zero = 0;
    for(ll x = 0; x + 1 < N; x++) {
        for(auto [y, w] : fish[x]) {
            up.range_chmax(y + 1, N + 1, up[y] + w);
        }
        reverse(fish[x + 1].begin(), fish[x + 1].end());
        for(auto [y, w] : fish[x + 1]) {
            down.range_chmax(0, y + 1, down[y + 1] + w);
        }
        reverse(fish[x + 1].begin(), fish[x + 1].end());
        const ll zero_ = exchange(zero, down[0]);
        down.range_chmax(0, N + 1, up[N]);
        up.range_chmax(0, N + 1, zero_);
    }
    return max({zero, down[0], up[N]});
}

Subtask #1
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	44 ms	8660 KB	Output is correct
2	Correct	55 ms	9920 KB	Output is correct
3	Correct	14 ms	5776 KB	Output is correct
4	Correct	12 ms	5716 KB	Output is correct
5	Correct	161 ms	18084 KB	Output is correct
6	Correct	222 ms	20676 KB	Output is correct

Subtask #2
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	98 ms	11980 KB	Output is correct
3	Correct	107 ms	14004 KB	Output is correct
4	Correct	46 ms	8572 KB	Output is correct
5	Correct	54 ms	10012 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	14 ms	5884 KB	Output is correct
11	Correct	12 ms	5716 KB	Output is correct
12	Correct	50 ms	8636 KB	Output is correct
13	Correct	60 ms	9892 KB	Output is correct
14	Correct	47 ms	8572 KB	Output is correct
15	Correct	54 ms	9592 KB	Output is correct
16	Correct	47 ms	8764 KB	Output is correct
17	Correct	60 ms	9528 KB	Output is correct

Subtask #3
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	5676 KB	Output is correct
2	Correct	12 ms	5716 KB	Output is correct
3	Incorrect	35 ms	8276 KB	1st lines differ - on the 1st token, expected: '21261825233649', found: '20897672610412'
4	Halted	0 ms	0 KB	-

Subtask #4
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	300 KB	Output is correct
4	Correct	1 ms	300 KB	Output is correct
5	Correct	0 ms	296 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	288 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Incorrect	1 ms	340 KB	1st lines differ - on the 1st token, expected: '216624184325', found: '214837477243'
10	Halted	0 ms	0 KB	-

Subtask #5
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	300 KB	Output is correct
4	Correct	1 ms	300 KB	Output is correct
5	Correct	0 ms	296 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	288 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Incorrect	1 ms	340 KB	1st lines differ - on the 1st token, expected: '216624184325', found: '214837477243'
10	Halted	0 ms	0 KB	-

Subtask #6
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	300 KB	Output is correct
4	Correct	1 ms	300 KB	Output is correct
5	Correct	0 ms	296 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	288 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Incorrect	1 ms	340 KB	1st lines differ - on the 1st token, expected: '216624184325', found: '214837477243'
10	Halted	0 ms	0 KB	-

Subtask #7
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	5676 KB	Output is correct
2	Correct	12 ms	5716 KB	Output is correct
3	Incorrect	35 ms	8276 KB	1st lines differ - on the 1st token, expected: '21261825233649', found: '20897672610412'
4	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	44 ms	8660 KB	Output is correct
2	Correct	55 ms	9920 KB	Output is correct
3	Correct	14 ms	5776 KB	Output is correct
4	Correct	12 ms	5716 KB	Output is correct
5	Correct	161 ms	18084 KB	Output is correct
6	Correct	222 ms	20676 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	98 ms	11980 KB	Output is correct
9	Correct	107 ms	14004 KB	Output is correct
10	Correct	46 ms	8572 KB	Output is correct
11	Correct	54 ms	10012 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	14 ms	5884 KB	Output is correct
17	Correct	12 ms	5716 KB	Output is correct
18	Correct	50 ms	8636 KB	Output is correct
19	Correct	60 ms	9892 KB	Output is correct
20	Correct	47 ms	8572 KB	Output is correct
21	Correct	54 ms	9592 KB	Output is correct
22	Correct	47 ms	8764 KB	Output is correct
23	Correct	60 ms	9528 KB	Output is correct
24	Correct	11 ms	5676 KB	Output is correct
25	Correct	12 ms	5716 KB	Output is correct
26	Incorrect	35 ms	8276 KB	1st lines differ - on the 1st token, expected: '21261825233649', found: '20897672610412'
27	Halted	0 ms	0 KB	-

답안 #667029

Compilation message