oj.uz

Submission #838241

# Submission time Handle Problem Language Result Execution time Memory
838241 2023-08-26T11:52:59 Z Theo830 Catfish Farm (IOI22_fish) C++17
64 / 100
 1000 ms 143892 KB 
#include "fish.h"
#include<bits/stdc++.h>
#define ii pair<int,long long>
#define F first
#define S second
#define iii pair<ii,int>
using namespace std;
long long dp[3000005][3];
vector<iii>pre[100005];
int n;
long long sum(int i,int j){
    if(i >= n){
        return 0;
    }
    int posi = lower_bound(pre[i].begin(),pre[i].end(),iii(ii(j+1,0),0)) - pre[i].begin();
    posi--;
    return pre[i][posi].F.S;
}
long long solve(int i,int j,int k){
    int pos = -1;
    long long sumi = 0;
    if(i >= n){
        return 0;
    }
    if(j < 0 || j > n){
        return 0;
    }
    if(k == 0 || k == 2){
        int posi = lower_bound(pre[i].begin(),pre[i].end(),iii(ii(j,0),0)) - pre[i].begin();
        j = pre[i][posi].F.F;
        pos = pre[i][posi].S;
    }
    else{
        int posi = lower_bound(pre[i].begin(),pre[i].end(),iii(ii(j+1,0),0)) - pre[i].begin();
        posi--;
        j = pre[i][posi].F.F;
        pos = pre[i][posi].S;
    }
    if(dp[pos][k] != -1){
        return dp[pos][k];
    }
    sumi = sum(i,j);
    long long ans = 0;
    if(k == 0 || k == 2){
        ans = max(ans,solve(i,j+1,k));
        long long val = 0;
        if(k == 0){
            val = sum(i-1,j);
        }
        long long sum2 = sum(i+1,j);
        ans = max(ans,solve(i+1,j,0) - sumi + val);
        ans = max(ans,solve(i+1,j,1) + val + sum2);
        ans = max(ans,solve(i+2,0,2) + val + sum2);
        ans = max(ans,solve(i+2,0,0) + val);
    }
    else{
        long long sum2 = sum(i+1,j);
        ans = max(ans,solve(i,j-1,1));
        ans = max(ans,solve(i+2,0,0) - sumi);
        ans = max(ans,solve(i+2,0,2) - sumi + sum2);
        ans = max(ans,solve(i+1,j,1) - sumi + sum2);
    }
    return dp[pos][k] = ans;
}
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W){
    n = N;
    memset(dp,-1,sizeof dp);
    long long sum = 0;
    for(int i = 0;i < M;i++){
        Y[i]++;
        pre[X[i]].push_back(iii(ii(Y[i],W[i]),0));
        pre[X[i]].push_back(iii(ii(Y[i] - 1,0),0));
        if(X[i] > 0){
            pre[X[i] - 1].push_back(iii(ii(Y[i],0),0));
        }
        if(X[i] < n-1){
            pre[X[i] + 1].push_back(iii(ii(Y[i],0),0));
        }
    }
    int cur = 0;
    for(int i = 0;i < N;i++){
        pre[i].push_back(iii(ii(0,0),0));
        pre[i].push_back(iii(ii(n,0),0));
        sort(pre[i].begin(),pre[i].end());
        int m = pre[i].size();
        pre[i][0].S = cur;
        cur++;
        for(int j = 1;j < m;j++){
            pre[i][j].F.S += pre[i][j-1].F.S;
            pre[i][j].S = cur;
            cur++;
        }
    }
    return solve(0,0,2);
}
/*
int main() {
  srand(time(0));
  int N = 2, M = 1;
  //assert(2 == scanf("%d %d", &N, &M));

  std::vector<int> X(M), Y(M), W(M);
  for (int i = 0; i < M; ++i) {
    W[i] = 1000000000;
    X[i] = 0;
    Y[i] = 0;
    //assert(3 == scanf("%d %d %d", &X[i], &Y[i], &W[i]));
  }

  long long result = max_weights(N, M, X, Y, W);
  printf("%lld\n", result);
  return 0;
}
*/

Compilation message

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:68:15: warning: unused variable 'sum' [-Wunused-variable]
   68 |     long long sum = 0;
      |               ^~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 111548 KB Output is correct
2 Correct 201 ms 117032 KB Output is correct
3 Correct 72 ms 93444 KB Output is correct
4 Correct 73 ms 93496 KB Output is correct
5 Execution timed out 1089 ms 143892 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 73060 KB Output is correct
2 Correct 320 ms 121212 KB Output is correct
3 Correct 375 ms 128704 KB Output is correct
4 Correct 176 ms 111420 KB Output is correct
5 Correct 198 ms 116972 KB Output is correct
6 Correct 26 ms 73036 KB Output is correct
7 Correct 27 ms 73004 KB Output is correct
8 Correct 27 ms 73044 KB Output is correct
9 Correct 28 ms 73024 KB Output is correct
10 Correct 77 ms 93428 KB Output is correct
11 Correct 88 ms 93424 KB Output is correct
12 Correct 260 ms 113560 KB Output is correct
13 Correct 302 ms 120032 KB Output is correct
14 Correct 231 ms 111972 KB Output is correct
15 Correct 220 ms 110060 KB Output is correct
16 Correct 235 ms 112000 KB Output is correct
17 Correct 250 ms 116220 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 93460 KB Output is correct
2 Correct 74 ms 93328 KB Output is correct
3 Correct 123 ms 101376 KB Output is correct
4 Correct 112 ms 99644 KB Output is correct
5 Correct 255 ms 111928 KB Output is correct
6 Correct 164 ms 111920 KB Output is correct
7 Correct 165 ms 111944 KB Output is correct
8 Correct 178 ms 111816 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 73032 KB Output is correct
2 Correct 32 ms 72960 KB Output is correct
3 Correct 28 ms 73076 KB Output is correct
4 Correct 28 ms 73080 KB Output is correct
5 Correct 27 ms 73008 KB Output is correct
6 Correct 28 ms 73032 KB Output is correct
7 Correct 31 ms 73040 KB Output is correct
8 Correct 28 ms 73000 KB Output is correct
9 Correct 29 ms 73176 KB Output is correct
10 Correct 30 ms 73684 KB Output is correct
11 Correct 29 ms 73224 KB Output is correct
12 Correct 31 ms 73356 KB Output is correct
13 Correct 29 ms 73060 KB Output is correct
14 Correct 30 ms 73304 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 73032 KB Output is correct
2 Correct 32 ms 72960 KB Output is correct
3 Correct 28 ms 73076 KB Output is correct
4 Correct 28 ms 73080 KB Output is correct
5 Correct 27 ms 73008 KB Output is correct
6 Correct 28 ms 73032 KB Output is correct
7 Correct 31 ms 73040 KB Output is correct
8 Correct 28 ms 73000 KB Output is correct
9 Correct 29 ms 73176 KB Output is correct
10 Correct 30 ms 73684 KB Output is correct
11 Correct 29 ms 73224 KB Output is correct
12 Correct 31 ms 73356 KB Output is correct
13 Correct 29 ms 73060 KB Output is correct
14 Correct 30 ms 73304 KB Output is correct
15 Correct 30 ms 73200 KB Output is correct
16 Correct 32 ms 73356 KB Output is correct
17 Correct 113 ms 79316 KB Output is correct
18 Correct 108 ms 81284 KB Output is correct
19 Correct 108 ms 81460 KB Output is correct
20 Correct 95 ms 81032 KB Output is correct
21 Correct 96 ms 80912 KB Output is correct
22 Correct 167 ms 88592 KB Output is correct
23 Correct 62 ms 74684 KB Output is correct
24 Correct 122 ms 78016 KB Output is correct
25 Correct 32 ms 73352 KB Output is correct
26 Correct 53 ms 74560 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 73032 KB Output is correct
2 Correct 32 ms 72960 KB Output is correct
3 Correct 28 ms 73076 KB Output is correct
4 Correct 28 ms 73080 KB Output is correct
5 Correct 27 ms 73008 KB Output is correct
6 Correct 28 ms 73032 KB Output is correct
7 Correct 31 ms 73040 KB Output is correct
8 Correct 28 ms 73000 KB Output is correct
9 Correct 29 ms 73176 KB Output is correct
10 Correct 30 ms 73684 KB Output is correct
11 Correct 29 ms 73224 KB Output is correct
12 Correct 31 ms 73356 KB Output is correct
13 Correct 29 ms 73060 KB Output is correct
14 Correct 30 ms 73304 KB Output is correct
15 Correct 30 ms 73200 KB Output is correct
16 Correct 32 ms 73356 KB Output is correct
17 Correct 113 ms 79316 KB Output is correct
18 Correct 108 ms 81284 KB Output is correct
19 Correct 108 ms 81460 KB Output is correct
20 Correct 95 ms 81032 KB Output is correct
21 Correct 96 ms 80912 KB Output is correct
22 Correct 167 ms 88592 KB Output is correct
23 Correct 62 ms 74684 KB Output is correct
24 Correct 122 ms 78016 KB Output is correct
25 Correct 32 ms 73352 KB Output is correct
26 Correct 53 ms 74560 KB Output is correct
27 Correct 33 ms 74188 KB Output is correct
28 Correct 422 ms 109200 KB Output is correct
29 Correct 646 ms 115416 KB Output is correct
30 Execution timed out 1085 ms 119976 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 93460 KB Output is correct
2 Correct 74 ms 93328 KB Output is correct
3 Correct 123 ms 101376 KB Output is correct
4 Correct 112 ms 99644 KB Output is correct
5 Correct 255 ms 111928 KB Output is correct
6 Correct 164 ms 111920 KB Output is correct
7 Correct 165 ms 111944 KB Output is correct
8 Correct 178 ms 111816 KB Output is correct
9 Correct 213 ms 111900 KB Output is correct
10 Correct 145 ms 103940 KB Output is correct
11 Correct 278 ms 134680 KB Output is correct
12 Correct 34 ms 73028 KB Output is correct
13 Correct 27 ms 73044 KB Output is correct
14 Correct 29 ms 73060 KB Output is correct
15 Correct 32 ms 73052 KB Output is correct
16 Correct 32 ms 72992 KB Output is correct
17 Correct 29 ms 73036 KB Output is correct
18 Correct 75 ms 93360 KB Output is correct
19 Correct 75 ms 93396 KB Output is correct
20 Correct 75 ms 93424 KB Output is correct
21 Correct 78 ms 93432 KB Output is correct
22 Correct 294 ms 110776 KB Output is correct
23 Correct 369 ms 134736 KB Output is correct
24 Correct 362 ms 134680 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 111548 KB Output is correct
2 Correct 201 ms 117032 KB Output is correct
3 Correct 72 ms 93444 KB Output is correct
4 Correct 73 ms 93496 KB Output is correct
5 Execution timed out 1089 ms 143892 KB Time limit exceeded
6 Halted 0 ms 0 KB -