답안 #635451

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
635451	2022-08-26T09:29:46 Z	OttoTheDino	메기 농장 (IOI22_fish)	C++17	6 / 100	757 ms	132616 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());
                    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
0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	300 ms	69808 KB	Output is correct
2	Correct	755 ms	81584 KB	Output is correct
3	Correct	140 ms	59064 KB	Output is correct
4	Correct	140 ms	59048 KB	Output is correct
5	Correct	757 ms	132616 KB	Output is correct
6	Incorrect	751 ms	118380 KB	1st lines differ - on the 1st token, expected: '300000000000000', found: '186114000000000'
7	Halted	0 ms	0 KB	-

Subtask #2
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	535 ms	84572 KB	Output is correct
3	Correct	615 ms	100376 KB	Output is correct
4	Correct	264 ms	70264 KB	Output is correct
5	Correct	421 ms	82120 KB	Output is correct
6	Correct	0 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	136 ms	59008 KB	Output is correct
11	Correct	134 ms	59040 KB	Output is correct
12	Correct	275 ms	70416 KB	Output is correct
13	Correct	305 ms	82164 KB	Output is correct
14	Correct	257 ms	70272 KB	Output is correct
15	Correct	301 ms	79160 KB	Output is correct
16	Correct	259 ms	70272 KB	Output is correct
17	Correct	286 ms	80348 KB	Output is correct

Subtask #3
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	140 ms	59152 KB	Output is correct
2	Correct	132 ms	59132 KB	Output is correct
3	Incorrect	222 ms	63988 KB	1st lines differ - on the 1st token, expected: '21261825233649', found: '16089992176629'
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	1 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: '188483049066'
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	1 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: '188483049066'
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	1 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: '188483049066'
10	Halted	0 ms	0 KB	-

Subtask #7
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	140 ms	59152 KB	Output is correct
2	Correct	132 ms	59132 KB	Output is correct
3	Incorrect	222 ms	63988 KB	1st lines differ - on the 1st token, expected: '21261825233649', found: '16089992176629'
4	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	300 ms	69808 KB	Output is correct
2	Correct	755 ms	81584 KB	Output is correct
3	Correct	140 ms	59064 KB	Output is correct
4	Correct	140 ms	59048 KB	Output is correct
5	Correct	757 ms	132616 KB	Output is correct
6	Incorrect	751 ms	118380 KB	1st lines differ - on the 1st token, expected: '300000000000000', found: '186114000000000'
7	Halted	0 ms	0 KB	-

답안 #635451

Compilation message