oj.uz

답안 #1070886

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1070886 2024-08-22T20:22:58 Z beaconmc 메기 농장 (IOI22_fish) C++17
6 / 100
 1000 ms 395708 KB 
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "fish.h"
 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
 
const ll maxn = 100005;
 
 
set<ll> heights[maxn];
basic_string<ll> realheights[maxn];
 
 
map<ll,ll> weights;
 
basic_string<ll> p[maxn];
 
basic_string<array<ll,2>>  dp[maxn];
 
basic_string<ll> pref[maxn][2];
basic_string<ll> pref2[maxn][2];
basic_string<ll> suff[maxn][2];
 
 
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {

 
    FOR(i,0,M){
        Y[i]++;
        weights[X[i]*100000000+Y[i]] = W[i];
 
        if (X[i] > 0) heights[X[i]-1].insert(Y[i]);
        if (X[i] > 1) heights[X[i]-2].insert(Y[i]);
        heights[X[i]].insert(Y[i]);
        heights[X[i]+1].insert(Y[i]);
        heights[X[i]+2].insert(Y[i]);
    }
    FOR(i,0,maxn) heights[i].insert(0);
    FOR(i,0,maxn) heights[i].insert(maxn);
 
    FOR(i,0,maxn){
        FOR(k,0,2){
            pref[i][k].resize(heights[i].size());
            pref2[i][k].resize(heights[i].size());
            suff[i][k].resize(heights[i].size());
        }
        p[i].resize(heights[i].size());
        dp[i].resize(heights[i].size());
    }
    FOR(i,0,maxn){
        for (auto k : heights[i]) realheights[i].push_back(k);
    }
 
 
 
    FOR(i,0,maxn){
        p[i][0] = 0;
        ll prev = 0;
        FOR(j,1,heights[i].size()){
            p[i][j] = p[i][j-1] + weights[i*100000000+realheights[i][j]];
        }
    }
 
 
 
    FOR(i,1,N+1){
 
        FOR(X,0,dp[i].size()){
            ll j = realheights[i][X];
            FOR(k,0,2){
 
 
                if (i<2) continue;
                ll temp = 0;
                ll add = 0;
                if (k==0){
                    if (X==dp[i].size()-1) continue;
                    ll down = upper_bound(realheights[i-1].begin(), realheights[i-1].end(), j) - realheights[i-1].begin() - 1;
 
                    temp = max(temp, suff[i-1][0][down] - p[i-1][down]);
                    temp = max(temp, suff[i-1][1][down] - p[i-1][down]);
 
                    // FOR(p,j+1,N+1){
                    //     if (fish[i-1][p]) add += weights[i-1][p];
                    //     temp = max(temp, dp[i-1][p][0] + add);
                    //     temp = max(temp, dp[i-1][p][1] + add);
                    // }
                }else{
                    ll down = upper_bound(realheights[i-1].begin(), realheights[i-1].end(), j) - realheights[i-1].begin() - 1;
                    ll down2 = upper_bound(realheights[i-2].begin(), realheights[i-2].end(), j) - realheights[i-2].begin() - 1;
 
 
                    temp = max(temp, pref[i-1][0][down]);
                    temp = max(temp, pref[i-1][1][down] + p[i-2][down2]);
 
                    // FOR(p,0,j+1) if (fish[i-2][p]) add += weights[i-2][p];
                    // FOR(p,0,j+1){
                    //     if (fish[i-2][p]) add -= weights[i-2][p];
                    //     temp = max(temp, dp[i-1][p][0]);
                    //     temp = max(temp, dp[i-1][p][1] + add);
                    // }
                }
 
 
                dp[i][X][k] = temp;
            }
        }
        ll sz = realheights[i].size();
 
        FOR(k,0,2){
            ll tempadd = 0;
            ll tempadd2 = 0;
 
 
            FOR(j,0,sz){
                tempadd += weights[i*100000000+realheights[i][j]];
                suff[i][k][j] = dp[i][j][k]+tempadd;
            }
 
            FOR(j,0,sz){
                tempadd2 -= weights[(i-1)*100000000+realheights[i][j]];
                pref[i][k][j] = dp[i][j][k] + tempadd2;
                pref2[i][k][j] = dp[i][j][k];
            }
            ll prev = 0;
            FOR(j,1,sz){
                pref[i][k][j] = max(pref[i][k][j], pref[i][k][j-1]);
                pref2[i][k][j] = max(pref2[i][k][j], pref2[i][k][j-1]);
 
            }
 
            FORNEG(j,sz-2,-1){
                suff[i][k][j] = max(suff[i][k][j], suff[i][k][j+1]);
 
 
            }
 
        }
        // cout << i << endl;
        // cout << suff[2][2][0] << "FUCK" << endl;
 
    }
 
 
    // cout << dp[3][2][0] << endl;
 
 
 
    ll ans = 0;
 
    FOR(i,0,N+1){
        FOR(j,0,dp[i].size()){
            ans = max(dp[i][j][0], ans);
            ans = max(dp[i][j][1], ans);
        }
    }
    return ans;
 
 
 
 
 
 
}

Compilation message

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:9:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::set<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
   65 |         FOR(j,1,heights[i].size()){
      |             ~~~~~~~~~~~~~~~~~~~~~
fish.cpp:65:9: note: in expansion of macro 'FOR'
   65 |         FOR(j,1,heights[i].size()){
      |         ^~~
fish.cpp:64:12: warning: unused variable 'prev' [-Wunused-variable]
   64 |         ll prev = 0;
      |            ^~~~
fish.cpp:9:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
   74 |         FOR(X,0,dp[i].size()){
      |             ~~~~~~~~~~~~~~~~     
fish.cpp:74:9: note: in expansion of macro 'FOR'
   74 |         FOR(X,0,dp[i].size()){
      |         ^~~
fish.cpp:83:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |                     if (X==dp[i].size()-1) continue;
      |                         ~^~~~~~~~~~~~~~~~
fish.cpp:81:20: warning: unused variable 'add' [-Wunused-variable]
   81 |                 ll add = 0;
      |                    ^~~
fish.cpp:131:16: warning: unused variable 'prev' [-Wunused-variable]
  131 |             ll prev = 0;
      |                ^~~~
fish.cpp:9:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
  158 |         FOR(j,0,dp[i].size()){
      |             ~~~~~~~~~~~~~~~~     
fish.cpp:158:9: note: in expansion of macro 'FOR'
  158 |         FOR(j,0,dp[i].size()){
      |         ^~~

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 436 ms 133212 KB Output is correct
2 Correct 517 ms 145076 KB Output is correct
3 Correct 154 ms 86356 KB Output is correct
4 Correct 145 ms 86284 KB Output is correct
5 Execution timed out 1088 ms 395708 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 80244 KB Output is correct
2 Correct 641 ms 155008 KB Output is correct
3 Correct 769 ms 166468 KB Output is correct
4 Correct 401 ms 133240 KB Output is correct
5 Correct 459 ms 145212 KB Output is correct
6 Correct 68 ms 80260 KB Output is correct
7 Correct 69 ms 80208 KB Output is correct
8 Correct 69 ms 80096 KB Output is correct
9 Correct 75 ms 80024 KB Output is correct
10 Correct 136 ms 86352 KB Output is correct
11 Correct 138 ms 86356 KB Output is correct
12 Correct 468 ms 148844 KB Output is correct
13 Correct 619 ms 163964 KB Output is correct
14 Correct 478 ms 141000 KB Output is correct
15 Correct 380 ms 125024 KB Output is correct
16 Correct 480 ms 141036 KB Output is correct
17 Correct 506 ms 147720 KB Output is correct

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 86352 KB Output is correct
2 Incorrect 150 ms 86508 KB 1st lines differ - on the 1st token, expected: '882019', found: '0'
3 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 80124 KB Output is correct
2 Correct 77 ms 80208 KB Output is correct
3 Correct 69 ms 80208 KB Output is correct
4 Correct 74 ms 80160 KB Output is correct
5 Correct 73 ms 80040 KB Output is correct
6 Correct 74 ms 80264 KB Output is correct
7 Correct 68 ms 80124 KB Output is correct
8 Correct 73 ms 80212 KB Output is correct
9 Incorrect 88 ms 80220 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '30688838905'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 80124 KB Output is correct
2 Correct 77 ms 80208 KB Output is correct
3 Correct 69 ms 80208 KB Output is correct
4 Correct 74 ms 80160 KB Output is correct
5 Correct 73 ms 80040 KB Output is correct
6 Correct 74 ms 80264 KB Output is correct
7 Correct 68 ms 80124 KB Output is correct
8 Correct 73 ms 80212 KB Output is correct
9 Incorrect 88 ms 80220 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '30688838905'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 80124 KB Output is correct
2 Correct 77 ms 80208 KB Output is correct
3 Correct 69 ms 80208 KB Output is correct
4 Correct 74 ms 80160 KB Output is correct
5 Correct 73 ms 80040 KB Output is correct
6 Correct 74 ms 80264 KB Output is correct
7 Correct 68 ms 80124 KB Output is correct
8 Correct 73 ms 80212 KB Output is correct
9 Incorrect 88 ms 80220 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '30688838905'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 86352 KB Output is correct
2 Incorrect 150 ms 86508 KB 1st lines differ - on the 1st token, expected: '882019', found: '0'
3 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 436 ms 133212 KB Output is correct
2 Correct 517 ms 145076 KB Output is correct
3 Correct 154 ms 86356 KB Output is correct
4 Correct 145 ms 86284 KB Output is correct
5 Execution timed out 1088 ms 395708 KB Time limit exceeded
6 Halted 0 ms 0 KB -