oj.uz

답안 #1023924

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1023924 2024-07-15T09:36:23 Z Otalp 메기 농장 (IOI22_fish) C++17
9 / 100
 870 ms 197244 KB 
#include "fish.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second

const int MAXN = 500100;
int n, w[MAXN], m;
pii a[MAXN];

namespace B{
    map<ll, ll> d[200100];
    map<ll, ll> dp[200100];
    map<ll, ll> pref[200100];
    map<ll, ll> ddp[200100];
    vector<ll> pos[200100];
    ll suf[200100];
    ll solve(){
        for(ll i=1; i<=m; i++){
            d[a[i].ff][a[i].ss] += w[i];
            pos[a[i].ff].pb(a[i].ss);
        }
        d[0][0] = 1;
        pos[0].pb(0);
        for(int i=0; i<=n; i++){
            d[i][n] = 0;
            pos[i].pb(n);
        }
        for(ll i=1; i<=n; i++){
            sort(pos[i].begin(), pos[i].end());
        }
        for(ll i=1; i<=n; i++){
            dp[0][i] = -1e18;
            ddp[0][i] = -1e18;
        }
        dp[0][0] = 0;
        ddp[0][0] = 0;
        for(ll i=1; i<=n; i++){
            //cout<<"_____________________\n";
            //cout<<i<<'\n';
            vector<ll> alpos;
            for(auto h: pos[i-1]) alpos.pb(h);
            for(auto h: pos[i+1]) alpos.pb(h);
            sort(alpos.begin(), alpos.end());
            for(ll  h: pos[i]){
                ll j = h;
                pref[i][j] = pref[i][j - 1] + d[i][j];
            }
            vector<ll> dpos;
            for(auto h: dp[i-1]){
                dpos.pb(h.ff);
            }
            ll mx = -1e18;
            ll ls = pos[i].size()-1;
            for(ll h = dpos.size()-1; h>=0; h--){
                ll j = dpos[h];
                while(ls > 0 and pos[i][ls] > j) ls--;
                mx = max(mx, dp[i-1][j] + pref[i][j]);
                suf[j] = mx;
            }
            ll pddp = -1e18, pdp = -1e18;
            mx = -1e18;
            for(ll h = dpos.size()-1; h>=0; h--){
                ll j = dpos[h];
                mx = max(mx, dp[i-1][j]);
            }
            ll pls=-1, dpls=-1;
            ls = -1;
            ll lls = -1;
            for(ll j: alpos){
                //cout<<j<<' ';
                while(ls + 1 < dpos.size() and dpos[ls + 1] <= j){
                    ls += 1;
                    while(lls + 1 < pos[i-1].size() and pos[i-1][lls + 1] <= dpos[ls]) lls++;
                    pdp = max(pdp, ddp[i-1][dpos[ls]]-pref[i-1][pos[i-1][lls]]);
                }
                while(pls + 1 < pos[i].size() and pos[i][pls + 1] <= j) pls ++;
                while(dpls + 1 < pos[i-1].size() and pos[i-1][dpls + 1] <= j) dpls ++;
                ddp[i][j] = mx;
                dp[i][j] = 0;
                //if(dpls < 0){
                //    cout<<"asdas\n";
                //    cout<<j<<'\n';
                //    cout<<dpls+1<<'\n';
                //    continue;
                //}
                ddp[i][j] = max(ddp[i][j], pdp + pref[i-1][pos[i-1][dpls]]);
                dp[i][j] = ddp[i][j];
                if(dpos.size() > ls + 1) dp[i][j] = max(dp[i][j], suf[dpos[ls + 1]]-pref[i][pos[i][pls]]);
                dp[i][j] = max(dp[i][j], pdp+pref[i-1][pos[i-1][dpls]]);
            }
            //cout<<'\n';
        }
        //for(ll i=1; i<=n; i++){
        //    for(ll j=0; j<=n; j++){
        //        cout<<dp[i][j]<<' ';
        //    }
        //    cout<<'\n';
        //}
        ll ans = 0;
        for(ll i=0; i<=n; i++) ans = max(ans, dp[n][i]);
        return ans;
    }
}




long long max_weights(int N, int M, vector<int> X, vector<int> Y,
                      vector<int> W) {
    
    n = N;
    m = M;
    for(int i=1; i<=m; i++){
        a[i] = {X[i-1]+1, Y[i-1]+1};
    }
    for(int i=1; i<=m; i++){
        w[i] = W[i-1];
    }
    for(int i=1; i<=n; i++){
        a[i + m] = {i, 0};
        w[i+m] = 0;
    }
    m += n;
    return B::solve();
}

Compilation message

fish.cpp: In function 'long long int B::solve()':
fish.cpp:75:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |                 while(ls + 1 < dpos.size() and dpos[ls + 1] <= j){
      |                       ~~~~~~~^~~~~~~~~~~~~
fish.cpp:77:35: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |                     while(lls + 1 < pos[i-1].size() and pos[i-1][lls + 1] <= dpos[ls]) lls++;
      |                           ~~~~~~~~^~~~~~~~~~~~~~~~~
fish.cpp:80:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |                 while(pls + 1 < pos[i].size() and pos[i][pls + 1] <= j) pls ++;
      |                       ~~~~~~~~^~~~~~~~~~~~~~~
fish.cpp:81:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |                 while(dpls + 1 < pos[i-1].size() and pos[i-1][dpls + 1] <= j) dpls ++;
      |                       ~~~~~~~~~^~~~~~~~~~~~~~~~~
fish.cpp:92:32: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   92 |                 if(dpos.size() > ls + 1) dp[i][j] = max(dp[i][j], suf[dpos[ls + 1]]-pref[i][pos[i][pls]]);
      |                    ~~~~~~~~~~~~^~~~~~~~
fish.cpp:64:16: warning: unused variable 'pddp' [-Wunused-variable]
   64 |             ll pddp = -1e18, pdp = -1e18;
      |                ^~~~

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 476 ms 149760 KB 1st lines differ - on the 1st token, expected: '40313272768926', found: '36638591909'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 42588 KB Output is correct
2 Incorrect 870 ms 189440 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '84649862111'
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 235 ms 135336 KB Output is correct
2 Correct 224 ms 135336 KB Output is correct
3 Correct 290 ms 144868 KB Output is correct
4 Correct 309 ms 148152 KB Output is correct
5 Correct 354 ms 168604 KB Output is correct
6 Correct 367 ms 168744 KB Output is correct
7 Correct 371 ms 168628 KB Output is correct
8 Correct 344 ms 168632 KB Output is correct

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 42584 KB Output is correct
2 Correct 21 ms 42620 KB Output is correct
3 Incorrect 27 ms 42588 KB 1st lines differ - on the 1st token, expected: '4044', found: '2022'
4 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 42584 KB Output is correct
2 Correct 21 ms 42620 KB Output is correct
3 Incorrect 27 ms 42588 KB 1st lines differ - on the 1st token, expected: '4044', found: '2022'
4 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 42584 KB Output is correct
2 Correct 21 ms 42620 KB Output is correct
3 Incorrect 27 ms 42588 KB 1st lines differ - on the 1st token, expected: '4044', found: '2022'
4 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 235 ms 135336 KB Output is correct
2 Correct 224 ms 135336 KB Output is correct
3 Correct 290 ms 144868 KB Output is correct
4 Correct 309 ms 148152 KB Output is correct
5 Correct 354 ms 168604 KB Output is correct
6 Correct 367 ms 168744 KB Output is correct
7 Correct 371 ms 168628 KB Output is correct
8 Correct 344 ms 168632 KB Output is correct
9 Correct 428 ms 193672 KB Output is correct
10 Correct 244 ms 119916 KB Output is correct
11 Correct 513 ms 197244 KB Output is correct
12 Incorrect 21 ms 42588 KB 1st lines differ - on the 1st token, expected: '4044', found: '2022'
13 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 476 ms 149760 KB 1st lines differ - on the 1st token, expected: '40313272768926', found: '36638591909'
2 Halted 0 ms 0 KB -