답안 #635500

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
635500	2022-08-26T10:45:55 Z	OttoTheDino	메기 농장 (IOI22_fish)	C++17	9 / 100	750 ms	133236 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);
                    //cout << "1: " << i << " " << y << " " << dp[i][0][y] << endl;
                }
                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]});
                if (tp==3) {
                    ll res = dp[i-1][0][n]+cur;
                    if (len(st)) res = max(res, *st.rbegin());
                    if (y==n) res = max(res, dp[i][0][n]+cur);
                    dp[i][1][y] = res-cur+sum;
                    //cout << "2: " << i << " " << y << " " << dp[i][1][y] << endl;
                    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	225 ms	69956 KB	Output is correct
2	Correct	268 ms	81988 KB	Output is correct
3	Correct	107 ms	58956 KB	Output is correct
4	Correct	106 ms	58956 KB	Output is correct
5	Correct	750 ms	133236 KB	Output is correct
6	Correct	690 ms	117988 KB	Output is correct

Subtask #2
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	430 ms	85368 KB	Output is correct
3	Correct	527 ms	101060 KB	Output is correct
4	Correct	230 ms	69776 KB	Output is correct
5	Correct	271 ms	81652 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	0 ms	212 KB	Output is correct
10	Correct	112 ms	59012 KB	Output is correct
11	Correct	107 ms	58964 KB	Output is correct
12	Correct	243 ms	69708 KB	Output is correct
13	Correct	303 ms	81620 KB	Output is correct
14	Correct	231 ms	69732 KB	Output is correct
15	Correct	272 ms	78528 KB	Output is correct
16	Correct	229 ms	69640 KB	Output is correct
17	Correct	267 ms	79700 KB	Output is correct

Subtask #3
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	117 ms	59044 KB	Output is correct
2	Correct	111 ms	59060 KB	Output is correct
3	Incorrect	173 ms	64176 KB	1st lines differ - on the 1st token, expected: '21261825233649', found: '26722445760742'
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	0 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	Incorrect	1 ms	468 KB	1st lines differ - on the 1st token, expected: '216624184325', found: '310323004046'
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	0 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	Incorrect	1 ms	468 KB	1st lines differ - on the 1st token, expected: '216624184325', found: '310323004046'
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	0 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	Incorrect	1 ms	468 KB	1st lines differ - on the 1st token, expected: '216624184325', found: '310323004046'
10	Halted	0 ms	0 KB	-

Subtask #7
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	117 ms	59044 KB	Output is correct
2	Correct	111 ms	59060 KB	Output is correct
3	Incorrect	173 ms	64176 KB	1st lines differ - on the 1st token, expected: '21261825233649', found: '26722445760742'
4	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	225 ms	69956 KB	Output is correct
2	Correct	268 ms	81988 KB	Output is correct
3	Correct	107 ms	58956 KB	Output is correct
4	Correct	106 ms	58956 KB	Output is correct
5	Correct	750 ms	133236 KB	Output is correct
6	Correct	690 ms	117988 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	430 ms	85368 KB	Output is correct
9	Correct	527 ms	101060 KB	Output is correct
10	Correct	230 ms	69776 KB	Output is correct
11	Correct	271 ms	81652 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	0 ms	212 KB	Output is correct
16	Correct	112 ms	59012 KB	Output is correct
17	Correct	107 ms	58964 KB	Output is correct
18	Correct	243 ms	69708 KB	Output is correct
19	Correct	303 ms	81620 KB	Output is correct
20	Correct	231 ms	69732 KB	Output is correct
21	Correct	272 ms	78528 KB	Output is correct
22	Correct	229 ms	69640 KB	Output is correct
23	Correct	267 ms	79700 KB	Output is correct
24	Correct	117 ms	59044 KB	Output is correct
25	Correct	111 ms	59060 KB	Output is correct
26	Incorrect	173 ms	64176 KB	1st lines differ - on the 1st token, expected: '21261825233649', found: '26722445760742'
27	Halted	0 ms	0 KB	-

답안 #635500

Compilation message