oj.uz

답안 #1069335

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1069335 2024-08-21T19:41:01 Z beaconmc 메기 농장 (IOI22_fish) C++17
23 / 100
 926 ms 110676 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;


unordered_set<ll> fish[maxn];

map<basic_string<ll>, ll> weights;

ll dp[5][5][maxn];

unordered_set<ll> temppos[maxn];
basic_string<ll> possibles[maxn];

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
    FOR(i,0,5){
        FOR(j,0,5){
            FOR(k,0,maxn){
                dp[i][j][k] = 0;
            }
        }
    }
    FOR(i,0,maxn) temppos[i].insert(0);


    FOR(i,0,M){
        Y[i]++;
        fish[X[i]].insert(Y[i]);
        weights[{X[i], Y[i]}] = W[i];
        if (X[i] > 0) temppos[X[i]-1].insert(Y[i]);
        temppos[X[i]+1].insert(Y[i]);

    }
    FOR(i,0,maxn){
        for (auto&k : temppos[i]) possibles[i].push_back(k);
    }
    FOR(i,0,maxn) sort(possibles[i].begin(), possibles[i].end());

    FOR(k,0,N){
        FOR(X,0,5){
            FOR(Y,0,5){
                ll i=0,j=0;
 
                if (k>=2 && possibles[k-2].size() <= X) continue;
                else if (k>=2) i = possibles[k-2][X];
                if (k>=1 && possibles[k-1].size() <= Y) continue;
                else if (k>=1) j  = possibles[k-1][Y];
                


                ll temp = 0;
                set<ll> visited;

                FOR(Z, 0, 5){
                    if (possibles[k].size() <= Z) continue;
                    ll height = possibles[k][Z];

                    if (fish[k+1].count(height)) temp += weights[{k+1, height}];

                    for (auto&p : fish[k]){
                        if (visited.count(p)==0 && j >= p && p<=height){
                            temp -= weights[{k, p}];
                            visited.insert(p);
                        }
                    }

                    if (k>0 && fish[k-1].count(height) && i < height && j<height) temp += weights[{k-1, height}];

                    dp[Y][Z][k+1] = max(dp[Y][Z][k+1], dp[X][Y][k] + temp);
                }
            }
        }
    }




    ll ans = 0;
    FOR(i,0,5){
        FOR(j,0,5){
            FOR(k,0,N+1){
                ans = max(ans, dp[i][j][k]);
                //if (dp[i][j][k]==11) cout << i << " " << j << " " << k << endl;

            }
        }
    }
    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:54:51: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   54 |                 if (k>=2 && possibles[k-2].size() <= X) continue;
      |                             ~~~~~~~~~~~~~~~~~~~~~~^~~~
fish.cpp:56:51: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   56 |                 if (k>=1 && possibles[k-1].size() <= Y) continue;
      |                             ~~~~~~~~~~~~~~~~~~~~~~^~~~
fish.cpp:65:45: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   65 |                     if (possibles[k].size() <= Z) continue;
      |                         ~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
0 / 3.0

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

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 48012 KB Output is correct
2 Incorrect 642 ms 88388 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '3006066943'
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 47956 KB Output is correct
2 Correct 38 ms 47952 KB Output is correct
3 Correct 153 ms 66404 KB Output is correct
4 Correct 105 ms 60496 KB Output is correct
5 Correct 219 ms 81748 KB Output is correct
6 Correct 231 ms 81828 KB Output is correct
7 Correct 242 ms 81748 KB Output is correct
8 Correct 237 ms 81748 KB Output is correct

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 47952 KB Output is correct
2 Correct 21 ms 47964 KB Output is correct
3 Correct 32 ms 48060 KB Output is correct
4 Correct 34 ms 47956 KB Output is correct
5 Correct 34 ms 47952 KB Output is correct
6 Correct 21 ms 47964 KB Output is correct
7 Correct 19 ms 47964 KB Output is correct
8 Correct 18 ms 47964 KB Output is correct
9 Correct 26 ms 48092 KB Output is correct
10 Incorrect 25 ms 48732 KB 1st lines differ - on the 1st token, expected: '799839985182', found: '407572246215'
11 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 47952 KB Output is correct
2 Correct 21 ms 47964 KB Output is correct
3 Correct 32 ms 48060 KB Output is correct
4 Correct 34 ms 47956 KB Output is correct
5 Correct 34 ms 47952 KB Output is correct
6 Correct 21 ms 47964 KB Output is correct
7 Correct 19 ms 47964 KB Output is correct
8 Correct 18 ms 47964 KB Output is correct
9 Correct 26 ms 48092 KB Output is correct
10 Incorrect 25 ms 48732 KB 1st lines differ - on the 1st token, expected: '799839985182', found: '407572246215'
11 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 47952 KB Output is correct
2 Correct 21 ms 47964 KB Output is correct
3 Correct 32 ms 48060 KB Output is correct
4 Correct 34 ms 47956 KB Output is correct
5 Correct 34 ms 47952 KB Output is correct
6 Correct 21 ms 47964 KB Output is correct
7 Correct 19 ms 47964 KB Output is correct
8 Correct 18 ms 47964 KB Output is correct
9 Correct 26 ms 48092 KB Output is correct
10 Incorrect 25 ms 48732 KB 1st lines differ - on the 1st token, expected: '799839985182', found: '407572246215'
11 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 47956 KB Output is correct
2 Correct 38 ms 47952 KB Output is correct
3 Correct 153 ms 66404 KB Output is correct
4 Correct 105 ms 60496 KB Output is correct
5 Correct 219 ms 81748 KB Output is correct
6 Correct 231 ms 81828 KB Output is correct
7 Correct 242 ms 81748 KB Output is correct
8 Correct 237 ms 81748 KB Output is correct
9 Correct 351 ms 86428 KB Output is correct
10 Correct 266 ms 75456 KB Output is correct
11 Correct 598 ms 102740 KB Output is correct
12 Correct 34 ms 47964 KB Output is correct
13 Correct 33 ms 47952 KB Output is correct
14 Correct 26 ms 47960 KB Output is correct
15 Correct 18 ms 47960 KB Output is correct
16 Correct 20 ms 47964 KB Output is correct
17 Correct 18 ms 48184 KB Output is correct
18 Correct 23 ms 47960 KB Output is correct
19 Correct 37 ms 47956 KB Output is correct
20 Correct 44 ms 47956 KB Output is correct
21 Correct 40 ms 48024 KB Output is correct
22 Correct 347 ms 82092 KB Output is correct
23 Correct 851 ms 109136 KB Output is correct
24 Correct 926 ms 110676 KB Output is correct

Subtask #8
0 / 16.0

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