Submission #1078930

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1078930	2024-08-28T08:19:55 Z	LittleOrange	Catfish Farm (IOI22_fish)	C++17	9 / 100	119 ms	34388 KB

fish

#include "fish.h"

#include <vector>
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

long long max_weights(int n, int m, std::vector<int> x, std::vector<int> y,
                      std::vector<int> w) {
  ll sub1 = 1, sub2 = 1, sub3 = 1;
  n++;
  vector<vector<pair<ll,ll>>> a(n);
  vector<vector<ll>> b(n);
  for(ll i = 0;i<m;i++){
    a[x[i]].push_back({y[i],w[i]});
    if(x[i]) b[x[i]-1].push_back(y[i]);
    b[x[i]+1].push_back(y[i]);
    if(x[i]&1) sub1 = 0;
    if(x[i]>1) sub2 = 0;
    if(y[i]) sub3 = 0;
  }
  for(auto &o : a) sort(o.begin(),o.end());
  for(auto &o : b) sort(o.begin(),o.end());
  if (sub1){
    ll ans = 0;
    for(ll i : w) ans += i;
    return ans;
  }
  if(sub2){
    ll a1 = 0, a2 = 0;
    vector<array<ll,3>> o;
    for(auto [p,v] : a[0]) a1+=v,o.push_back({p,1,v});
    for(auto [p,v] : a[1]) a2+=v,o.push_back({p,0,v});
    ll ans = max(a1,a2);
    if(n>3){
      sort(o.begin(),o.end());
      ll dp0 = 0, dp1 = 0;
      for(auto &u : o){
        if (u[1]){
          dp0 += u[2];
          dp1 = max(dp1,dp0);
        }else{
          dp1 += u[2];
        }
      }
      ans = max(ans,dp1);
    }
    return ans;
  }
  if (sub3){
    vector<ll> dp(n+1,0);
    for(ll i = 0;i<n;i++){
      dp[i+1] = dp[i];
      if(a[i].size()){
        ll v = a[i][0].second;
        if (i>=1&&a[i-1].size()) v += a[i-1][0].second;;
        if (i>=3) v += dp[i-3];
        dp[i+1] = max(dp[i+1],v);
        v = a[i][0].second;
        if (i>=2&&a[i-2].size()) v += a[i-2][0].second;;
        if (i>=3) v += dp[i-3];
        dp[i+1] = max(dp[i+1],v);
        v = a[i][0].second;
        if (i>=2) v += dp[i-2];
        dp[i+1] = max(dp[i+1],v);
      }
    }
    return dp.back();
  }
  return 0;
}

Subtask #1
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	10948 KB	Output is correct
2	Correct	34 ms	12588 KB	Output is correct
3	Correct	3 ms	5208 KB	Output is correct
4	Correct	2 ms	4952 KB	Output is correct
5	Correct	119 ms	30440 KB	Output is correct
6	Correct	117 ms	34388 KB	Output is correct

Subtask #2
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	87 ms	23860 KB	Output is correct
3	Correct	101 ms	26924 KB	Output is correct
4	Correct	28 ms	10956 KB	Output is correct
5	Correct	37 ms	12480 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	344 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	2 ms	4956 KB	Output is correct
11	Correct	2 ms	5100 KB	Output is correct
12	Correct	41 ms	15552 KB	Output is correct
13	Correct	49 ms	17488 KB	Output is correct
14	Correct	36 ms	14348 KB	Output is correct
15	Correct	53 ms	15416 KB	Output is correct
16	Correct	36 ms	14388 KB	Output is correct
17	Correct	39 ms	15292 KB	Output is correct

Subtask #3
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4956 KB	Output is correct
2	Correct	3 ms	5908 KB	Output is correct
3	Incorrect	42 ms	10896 KB	1st lines differ - on the 1st token, expected: '21261825233649', found: '18019359923151'
4	Halted	0 ms	0 KB	-

Subtask #4
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	344 KB	1st lines differ - on the 1st token, expected: '3', found: '0'
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	344 KB	1st lines differ - on the 1st token, expected: '3', found: '0'
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	344 KB	1st lines differ - on the 1st token, expected: '3', found: '0'
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4956 KB	Output is correct
2	Correct	3 ms	5908 KB	Output is correct
3	Incorrect	42 ms	10896 KB	1st lines differ - on the 1st token, expected: '21261825233649', found: '18019359923151'
4	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	10948 KB	Output is correct
2	Correct	34 ms	12588 KB	Output is correct
3	Correct	3 ms	5208 KB	Output is correct
4	Correct	2 ms	4952 KB	Output is correct
5	Correct	119 ms	30440 KB	Output is correct
6	Correct	117 ms	34388 KB	Output is correct
7	Correct	1 ms	344 KB	Output is correct
8	Correct	87 ms	23860 KB	Output is correct
9	Correct	101 ms	26924 KB	Output is correct
10	Correct	28 ms	10956 KB	Output is correct
11	Correct	37 ms	12480 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	1 ms	344 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	2 ms	4956 KB	Output is correct
17	Correct	2 ms	5100 KB	Output is correct
18	Correct	41 ms	15552 KB	Output is correct
19	Correct	49 ms	17488 KB	Output is correct
20	Correct	36 ms	14348 KB	Output is correct
21	Correct	53 ms	15416 KB	Output is correct
22	Correct	36 ms	14388 KB	Output is correct
23	Correct	39 ms	15292 KB	Output is correct
24	Correct	3 ms	4956 KB	Output is correct
25	Correct	3 ms	5908 KB	Output is correct
26	Incorrect	42 ms	10896 KB	1st lines differ - on the 1st token, expected: '21261825233649', found: '18019359923151'
27	Halted	0 ms	0 KB	-

Submission #1078930

Compilation message