oj.uz

Submission #626886

# Submission time Handle Problem Language Result Execution time Memory
626886 2022-08-11T23:17:42 Z Monchito Catfish Farm (IOI22_fish) C++17
53 / 100
 1000 ms 18916 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;

#define fst first
#define snd second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()

typedef long long ll;
typedef vector<int> vi;

const int MAXN = 1e5 + 2;

int n, m;
vector<pair<int,ll>> a[MAXN];

ll solve1(){
  ll sum=0;
  for(int i=0; i<n; i++){
    for(auto& [y, w] : a[i]) sum += w;
  }
  return sum;
}

ll solve2(){
  ll res1=0, res2=0, res3=0;
  for(auto& [y, w] : a[0]) res1 += w;
  for(auto& [y, w] : a[1]) res2 += w;

  if(n>2){
    res3=res2;
    ll acc=res2;
    int i=0, j=0;
    for(int h=0; h<n; h++){
      while(j<sz(a[1]) && a[1][j].fst<=h) acc -= a[1][j++].snd;
      while(i<sz(a[0]) && a[0][i].fst<=h) acc += a[0][i++].snd;
      res3=max(res3,acc);
    }
  }
  return max(res1,max(res2,res3));
}

ll dp1[MAXN][2];
ll solve3(int i, int flag){
  if(i==n) return 0;
  ll& ret = dp1[i][flag];
  if(ret != -1) return ret;
  ret = solve3(i+1, 1);
  if(sz(a[i])){
    if(flag==1) ret=max(ret,a[i][0].snd+solve3(i+1,0));
    if(i<n-1) ret=max(ret,a[i][0].snd+solve3(i+2,1));
  }
  return ret;
}

ll dp2[300][1000];

ll solve4(int i, int v){
  if(i==n) return 0;
  ll& ret = dp2[i][v];
  if(ret != -1) return ret;

  int prev_used = (v <= n) ? v : 0, curr_used = (v > n) ? v - n : 0;

  int l=-1,r=-1;
  ll acc=0;
  for(int j=0; j<sz(a[i]); j++){
    if(a[i][j].fst < curr_used) continue;
    if(l==-1) l=r=j;
    if(a[i][j].fst < prev_used) acc+=a[i][j].snd, r++;
    else break;
  }

  ret = solve4(i+1, 0) + acc;
  ll curr=acc;
  for(int h=0; h<n; h++){
    while(l<r && a[i][l].fst <= h) curr-=a[i][l++].snd;
    ret=max(ret,curr+solve4(i+1, h+1));
  }
  if(i<n-1 && r!=-1){
    for(int j=r; j<sz(a[i]); j++){
      acc += a[i][j].snd;
      ret=max(ret, acc+solve4(i+1, a[i][j].fst+1+n));
    }
  }
  return ret;
}

ll max_weights(int N, int M, vi X, vi Y, vi W) {
  bool subtask1=true, subtask2=true, subtask3=true, subtask4_5=n<=300;
  n = N, m = M;
  for(int i=0; i<m; i++){
    subtask1 &= X[i] % 2 == 0;
    subtask2 &= X[i] <= 1;
    subtask3 &= Y[i] == 0;
    a[X[i]].pb(mp(Y[i], ll(W[i])));
  }
  for(int i=0; i<n; i++) sort(all(a[i]));

  if(subtask1) return solve1();
  if(subtask2) return solve2();
  if(subtask3){
    memset(dp1,-1,sizeof(dp1));
    return solve3(0, 0);
  }
  if(subtask4_5){
    memset(dp2, -1, sizeof(dp2));
    return solve4(0, 0);
  }
  return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 7956 KB Output is correct
2 Correct 42 ms 7412 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 131 ms 15876 KB Output is correct
6 Correct 128 ms 18308 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 63 ms 12404 KB Output is correct
3 Correct 83 ms 10928 KB Output is correct
4 Correct 35 ms 6984 KB Output is correct
5 Correct 40 ms 7392 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 2 ms 2660 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2660 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 35 ms 6992 KB Output is correct
13 Correct 38 ms 7368 KB Output is correct
14 Correct 39 ms 6496 KB Output is correct
15 Correct 38 ms 6716 KB Output is correct
16 Correct 33 ms 6472 KB Output is correct
17 Correct 37 ms 6692 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 7 ms 12004 KB Output is correct
3 Correct 28 ms 15000 KB Output is correct
4 Correct 22 ms 14244 KB Output is correct
5 Correct 48 ms 17612 KB Output is correct
6 Correct 54 ms 18232 KB Output is correct
7 Correct 47 ms 18852 KB Output is correct
8 Correct 46 ms 18916 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 2656 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2648 KB Output is correct
6 Correct 1 ms 2648 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 3 ms 4956 KB Output is correct
9 Correct 18 ms 4948 KB Output is correct
10 Correct 129 ms 5172 KB Output is correct
11 Correct 19 ms 5060 KB Output is correct
12 Correct 116 ms 5096 KB Output is correct
13 Correct 5 ms 4964 KB Output is correct
14 Correct 120 ms 5080 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 2656 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2648 KB Output is correct
6 Correct 1 ms 2648 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 3 ms 4956 KB Output is correct
9 Correct 18 ms 4948 KB Output is correct
10 Correct 129 ms 5172 KB Output is correct
11 Correct 19 ms 5060 KB Output is correct
12 Correct 116 ms 5096 KB Output is correct
13 Correct 5 ms 4964 KB Output is correct
14 Correct 120 ms 5080 KB Output is correct
15 Correct 128 ms 5032 KB Output is correct
16 Correct 7 ms 5076 KB Output is correct
17 Correct 282 ms 7768 KB Output is correct
18 Correct 280 ms 8384 KB Output is correct
19 Correct 252 ms 8236 KB Output is correct
20 Correct 253 ms 8220 KB Output is correct
21 Correct 248 ms 8148 KB Output is correct
22 Correct 447 ms 11420 KB Output is correct
23 Correct 167 ms 5628 KB Output is correct
24 Correct 250 ms 6932 KB Output is correct
25 Correct 126 ms 5096 KB Output is correct
26 Correct 158 ms 5584 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 2656 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2648 KB Output is correct
6 Correct 1 ms 2648 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 3 ms 4956 KB Output is correct
9 Correct 18 ms 4948 KB Output is correct
10 Correct 129 ms 5172 KB Output is correct
11 Correct 19 ms 5060 KB Output is correct
12 Correct 116 ms 5096 KB Output is correct
13 Correct 5 ms 4964 KB Output is correct
14 Correct 120 ms 5080 KB Output is correct
15 Correct 128 ms 5032 KB Output is correct
16 Correct 7 ms 5076 KB Output is correct
17 Correct 282 ms 7768 KB Output is correct
18 Correct 280 ms 8384 KB Output is correct
19 Correct 252 ms 8236 KB Output is correct
20 Correct 253 ms 8220 KB Output is correct
21 Correct 248 ms 8148 KB Output is correct
22 Correct 447 ms 11420 KB Output is correct
23 Correct 167 ms 5628 KB Output is correct
24 Correct 250 ms 6932 KB Output is correct
25 Correct 126 ms 5096 KB Output is correct
26 Correct 158 ms 5584 KB Output is correct
27 Execution timed out 1089 ms 5100 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 7 ms 12004 KB Output is correct
3 Correct 28 ms 15000 KB Output is correct
4 Correct 22 ms 14244 KB Output is correct
5 Correct 48 ms 17612 KB Output is correct
6 Correct 54 ms 18232 KB Output is correct
7 Correct 47 ms 18852 KB Output is correct
8 Correct 46 ms 18916 KB Output is correct
9 Execution timed out 1083 ms 10600 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 7956 KB Output is correct
2 Correct 42 ms 7412 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 131 ms 15876 KB Output is correct
6 Correct 128 ms 18308 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 63 ms 12404 KB Output is correct
9 Correct 83 ms 10928 KB Output is correct
10 Correct 35 ms 6984 KB Output is correct
11 Correct 40 ms 7392 KB Output is correct
12 Correct 1 ms 2644 KB Output is correct
13 Correct 2 ms 2660 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct
16 Correct 2 ms 2660 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Correct 35 ms 6992 KB Output is correct
19 Correct 38 ms 7368 KB Output is correct
20 Correct 39 ms 6496 KB Output is correct
21 Correct 38 ms 6716 KB Output is correct
22 Correct 33 ms 6472 KB Output is correct
23 Correct 37 ms 6692 KB Output is correct
24 Correct 2 ms 2644 KB Output is correct
25 Correct 7 ms 12004 KB Output is correct
26 Correct 28 ms 15000 KB Output is correct
27 Correct 22 ms 14244 KB Output is correct
28 Correct 48 ms 17612 KB Output is correct
29 Correct 54 ms 18232 KB Output is correct
30 Correct 47 ms 18852 KB Output is correct
31 Correct 46 ms 18916 KB Output is correct
32 Correct 4 ms 4948 KB Output is correct
33 Correct 3 ms 4948 KB Output is correct
34 Correct 2 ms 2656 KB Output is correct
35 Correct 1 ms 2644 KB Output is correct
36 Correct 2 ms 2648 KB Output is correct
37 Correct 1 ms 2648 KB Output is correct
38 Correct 1 ms 2648 KB Output is correct
39 Correct 3 ms 4956 KB Output is correct
40 Correct 18 ms 4948 KB Output is correct
41 Correct 129 ms 5172 KB Output is correct
42 Correct 19 ms 5060 KB Output is correct
43 Correct 116 ms 5096 KB Output is correct
44 Correct 5 ms 4964 KB Output is correct
45 Correct 120 ms 5080 KB Output is correct
46 Correct 128 ms 5032 KB Output is correct
47 Correct 7 ms 5076 KB Output is correct
48 Correct 282 ms 7768 KB Output is correct
49 Correct 280 ms 8384 KB Output is correct
50 Correct 252 ms 8236 KB Output is correct
51 Correct 253 ms 8220 KB Output is correct
52 Correct 248 ms 8148 KB Output is correct
53 Correct 447 ms 11420 KB Output is correct
54 Correct 167 ms 5628 KB Output is correct
55 Correct 250 ms 6932 KB Output is correct
56 Correct 126 ms 5096 KB Output is correct
57 Correct 158 ms 5584 KB Output is correct
58 Execution timed out 1089 ms 5100 KB Time limit exceeded
59 Halted 0 ms 0 KB -