답안 #635468

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
635468	2022-08-26T10:00:55 Z	OttoTheDino	메기 농장 (IOI22_fish)	C++17	9 / 100	726 ms	132408 KB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;

#define rep(i,s,e)              for (ll i = s; i <= e; ++i)
#define rrep(i,s,e)             for (ll i = s; i >= e; --i)
#define len(v)                  (ll)v.size()
#define pb                      push_back
#define all(v)                  v.begin(), v.end()
#define fi                      first
#define se                      second
typedef long long ll;
typedef vector<int> vi;
typedef pair<ll,ll> ii;
typedef pair<ll,ll> pll;

ll max_weights(int n, int m, vi X, vi Y, vi W) {
    bool done[n+5] = {};
    vector<ll> check[n+5], fish[n+5];
    unordered_map<ll,ll> w[n+5], dp[n+5][2];

    rep (i,0,m-1) {
        fish[X[i]+1].pb(Y[i]+1);
        w[X[i]+1][Y[i]+1] = W[i];
        check[X[i]+1].pb(Y[i]);
        if (Y[i]==0) done[X[i]+1] = 1;
    }

    rep (i,0,n) {
        if (i) check[i].pb(n);
        if (!done[i]) check[i].pb(0);
    }

    rep (i,1,n) {

        {
            //go bigger
            vector<pll> upd;
            set<ll> st;
            for (ll el : check[i]) upd.pb({el,1});
            for (ll el : fish[i-1]) upd.pb({el,0});
            for (ll el : check[i-1]) upd.pb({el,2});
            sort (all(upd));
            ll sum = 0;
            for (pll el : upd) {
                ll y = el.fi, tp = el.se;
                if (tp==0) {
                    sum += w[i-1][y]; 
                }
                if (tp==1) {
                    ll res;
                    if (len(st)) {
                        res = sum+*st.rbegin();
                    }
                    else res = 0;
                    dp[i][0][y] = max(dp[i][0][y], res);
                }
                if (tp==2) {
                    st.insert(dp[i-1][0][y]-sum);
                }
            }
        }

        {
            //go smaller
            vector<pll> upd;
            ll sum = 0, cur = 0;
            for (ll el : check[i]) upd.pb({el,3});
            for (ll el : fish[i+1]) {
                upd.pb({el, 0});
                sum += w[i+1][el]; 
            }
            for (ll el : fish[i]) {
                upd.pb({el, 1});
                cur += w[i][el];
            }
            for (ll el : check[i-1]) upd.pb ({el, 2});
            sort (all(upd));
            reverse(all(upd));
            set<ll> st;
            for (pll el : upd) {
                ll y = el.fi, tp = el.se;
                if (tp==0) sum -= w[i+1][y]; 
                if (tp==1) cur -= w[i][y];
                if (tp==2) st.insert({dp[i-1][1][y]+cur});
                if (tp==3) {
                    ll res = dp[i-1][0][n];
                    if (len(st)) res = max(res, *st.rbegin());
                    if (y==n) res = max(res, dp[i][0][n]);
                    dp[i][1][y] = res;
                    dp[i+1][0][y] = dp[i][1][y];
                }
            }
        }
    }

    ll ans = 0;
    for (ll y : check[n]) {
        ans = max(ans, dp[n][0][y]);
        ans = max(ans, dp[n][1][y]);
    }

    return ans;
}

Subtask #1
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	234 ms	69480 KB	Output is correct
2	Correct	278 ms	81352 KB	Output is correct
3	Correct	118 ms	58968 KB	Output is correct
4	Correct	123 ms	58960 KB	Output is correct
5	Correct	726 ms	132408 KB	Output is correct
6	Correct	712 ms	117776 KB	Output is correct

Subtask #2
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	436 ms	84564 KB	Output is correct
3	Correct	543 ms	100480 KB	Output is correct
4	Correct	231 ms	69624 KB	Output is correct
5	Correct	272 ms	81516 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	212 KB	Output is correct
10	Correct	121 ms	59076 KB	Output is correct
11	Correct	118 ms	59044 KB	Output is correct
12	Correct	242 ms	69732 KB	Output is correct
13	Correct	286 ms	81536 KB	Output is correct
14	Correct	231 ms	69620 KB	Output is correct
15	Correct	284 ms	78556 KB	Output is correct
16	Correct	244 ms	69648 KB	Output is correct
17	Correct	269 ms	79856 KB	Output is correct

Subtask #3
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	121 ms	59064 KB	Output is correct
2	Correct	122 ms	59164 KB	Output is correct
3	Incorrect	193 ms	63968 KB	1st lines differ - on the 1st token, expected: '21261825233649', found: '20269196083211'
4	Halted	0 ms	0 KB	-

Subtask #4
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	216 KB	Output is correct
5	Correct	0 ms	216 KB	Output is correct
6	Correct	1 ms	220 KB	Output is correct
7	Correct	1 ms	216 KB	Output is correct
8	Correct	0 ms	216 KB	Output is correct
9	Incorrect	1 ms	468 KB	1st lines differ - on the 1st token, expected: '216624184325', found: '229134181894'
10	Halted	0 ms	0 KB	-

Subtask #5
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	216 KB	Output is correct
5	Correct	0 ms	216 KB	Output is correct
6	Correct	1 ms	220 KB	Output is correct
7	Correct	1 ms	216 KB	Output is correct
8	Correct	0 ms	216 KB	Output is correct
9	Incorrect	1 ms	468 KB	1st lines differ - on the 1st token, expected: '216624184325', found: '229134181894'
10	Halted	0 ms	0 KB	-

Subtask #6
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	216 KB	Output is correct
5	Correct	0 ms	216 KB	Output is correct
6	Correct	1 ms	220 KB	Output is correct
7	Correct	1 ms	216 KB	Output is correct
8	Correct	0 ms	216 KB	Output is correct
9	Incorrect	1 ms	468 KB	1st lines differ - on the 1st token, expected: '216624184325', found: '229134181894'
10	Halted	0 ms	0 KB	-

Subtask #7
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	121 ms	59064 KB	Output is correct
2	Correct	122 ms	59164 KB	Output is correct
3	Incorrect	193 ms	63968 KB	1st lines differ - on the 1st token, expected: '21261825233649', found: '20269196083211'
4	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	234 ms	69480 KB	Output is correct
2	Correct	278 ms	81352 KB	Output is correct
3	Correct	118 ms	58968 KB	Output is correct
4	Correct	123 ms	58960 KB	Output is correct
5	Correct	726 ms	132408 KB	Output is correct
6	Correct	712 ms	117776 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	436 ms	84564 KB	Output is correct
9	Correct	543 ms	100480 KB	Output is correct
10	Correct	231 ms	69624 KB	Output is correct
11	Correct	272 ms	81516 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	121 ms	59076 KB	Output is correct
17	Correct	118 ms	59044 KB	Output is correct
18	Correct	242 ms	69732 KB	Output is correct
19	Correct	286 ms	81536 KB	Output is correct
20	Correct	231 ms	69620 KB	Output is correct
21	Correct	284 ms	78556 KB	Output is correct
22	Correct	244 ms	69648 KB	Output is correct
23	Correct	269 ms	79856 KB	Output is correct
24	Correct	121 ms	59064 KB	Output is correct
25	Correct	122 ms	59164 KB	Output is correct
26	Incorrect	193 ms	63968 KB	1st lines differ - on the 1st token, expected: '21261825233649', found: '20269196083211'
27	Halted	0 ms	0 KB	-

답안 #635468

Compilation message