oj.uz

답안 #1079050

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1079050 2024-08-28T09:59:20 Z LittleOrange 메기 농장 (IOI22_fish) C++17
32 / 100
 1000 ms 40168 KB 
#include "fish.h"

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

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;
  vector<vector<pair<ll,ll>>> a(n+1);
  vector<vector<ll>> b(n+1,vector<ll>(1,-1));
  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]);
    b[x[i]].push_back(y[i]);
    if(x[i]&1) sub1 = 0;
    if(x[i]>1) sub2 = 0;
    if(y[i]) sub3 = 0;
  }
  //cerr << sub1 << " " << sub2 << " " << sub3 << "\n";
  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>2){
      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){
    ll ans = 0;
    for(ll i : w) ans += i;
    vector<ll> dp(n+1,big);
    dp[0] = 0;
    for(ll i = 0;i<n;i++){
      ll cur = a[i].size()?a[i][0].second:0;
      dp[i+1] = min(dp[i+1],dp[i]+cur);
      if(i>=1)dp[i+1] = min(dp[i+1],dp[i-1]+cur);
      if(i>=3)dp[i+1] = min(dp[i+1],dp[i-2]+cur);
    }
    //for(ll i = 0;i<=n;i++) cerr << dp[i] << " \n"[i==n];
    ll de = min(dp.back(),dp.end()[-2]);
    return ans-de;
  }
  vector<vector<ll>> dp = b;
  for(auto &o : dp)fill(o.begin(),o.end(),0);
  vector<vector<ll>> dp0 = dp;
  for(auto &o : a){
    for(ll i = 1;i<o.size();i++){
      o[i].second += o[i-1].second;
    }
  }
  //for(auto &o : b){
  //  for(ll i = 0;i<o.size();i++) cout << o[i] << " \n"[i+1==o.size()];
  //}
  auto qry = [&](ll i, ll l, ll r){
    if(i<0||i>=n) return 0ll;
    auto &o = a[i];
    auto v1 = lower_bound(o.begin(),o.end(),make_pair(l+1,0ll));
    auto v2 = lower_bound(o.begin(),o.end(),make_pair(r+1,0ll));
    ll g1 = v1==o.begin()?0:(*--v1).second;
    ll g2 = v2==o.begin()?0:(*--v2).second;
    //cerr << "qry " << i << " " << l << " " << r << " = " << g2-g1 << "\n";
    return g2-g1;
  };
  ll ans = 0;
  for(ll i = 1;i<n;i++){
    for(ll j = 0;j<b[i].size();j++){
      ll y = b[i][j];
      for(ll k = 0;k<b[i-1].size();k++){
        ll y0 = b[i-1][k];
        ll cur = dp0[i-1][k];
        if(y0<y) cur += qry(i-1,y0,y);
        dp0[i][j] = max(dp0[i][j],cur);
        if(y0>y) cur += qry(i,y,y0);
        dp[i][j] = max(dp[i][j],cur);
      }
      if(i>1)for(ll k = 0;k<b[i-2].size();k++){
        ll y0 = b[i-2][k];
        ll cur = dp[i-2][k];
        ll h = max(y,y0);
        cur += qry(i-1,-1,h);
        dp[i][j] = max(dp[i][j],cur);
        dp0[i][j] = max(dp0[i][j],cur);
      }
      if(i>2)for(ll k = 0;k<b[i-3].size();k++){
        ll y0 = b[i-3][k];
        ll cur = dp[i-3][k];
        cur += qry(i-2,-1,y0);
        cur += qry(i-1,-1,y);
        dp[i][j] = max(dp[i][j],cur);
        dp0[i][j] = max(dp0[i][j],cur);
      }
      ans = max(ans,dp[i][j]+qry(i+1,-1,y));
      ans = max(ans,dp0[i][j]+qry(i+1,-1,y));
      //cerr << "dp " << i << " " << j << " = " << dp[i][j] << "\n";
    }
  }
  return ans;
  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:71:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(ll i = 1;i<o.size();i++){
      |                  ~^~~~~~~~~
fish.cpp:90:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for(ll j = 0;j<b[i].size();j++){
      |                  ~^~~~~~~~~~~~
fish.cpp:92:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |       for(ll k = 0;k<b[i-1].size();k++){
      |                    ~^~~~~~~~~~~~~~
fish.cpp:100:28: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |       if(i>1)for(ll k = 0;k<b[i-2].size();k++){
      |                           ~^~~~~~~~~~~~~~
fish.cpp:108:28: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |       if(i>2)for(ll k = 0;k<b[i-3].size();k++){
      |                           ~^~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 12536 KB Output is correct
2 Correct 47 ms 13880 KB Output is correct
3 Correct 7 ms 8028 KB Output is correct
4 Correct 6 ms 8268 KB Output is correct
5 Correct 142 ms 29536 KB Output is correct
6 Correct 143 ms 33376 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 99 ms 26432 KB Output is correct
3 Correct 124 ms 31344 KB Output is correct
4 Correct 36 ms 14128 KB Output is correct
5 Correct 44 ms 15668 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 7 ms 8116 KB Output is correct
11 Correct 8 ms 8276 KB Output is correct
12 Correct 51 ms 18600 KB Output is correct
13 Correct 62 ms 20760 KB Output is correct
14 Correct 44 ms 17512 KB Output is correct
15 Correct 59 ms 18968 KB Output is correct
16 Correct 47 ms 17548 KB Output is correct
17 Correct 51 ms 18872 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 8028 KB Output is correct
2 Correct 8 ms 9008 KB Output is correct
3 Correct 26 ms 12124 KB Output is correct
4 Correct 25 ms 11500 KB Output is correct
5 Correct 47 ms 16212 KB Output is correct
6 Correct 46 ms 16208 KB Output is correct
7 Correct 45 ms 16212 KB Output is correct
8 Correct 52 ms 16216 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 14 ms 856 KB Output is correct
11 Correct 3 ms 344 KB Output is correct
12 Correct 4 ms 652 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 3 ms 604 KB Output is correct

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 14 ms 856 KB Output is correct
11 Correct 3 ms 344 KB Output is correct
12 Correct 4 ms 652 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 3 ms 604 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 85 ms 604 KB Output is correct
17 Execution timed out 1038 ms 6744 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 14 ms 856 KB Output is correct
11 Correct 3 ms 344 KB Output is correct
12 Correct 4 ms 652 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 3 ms 604 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 85 ms 604 KB Output is correct
17 Execution timed out 1038 ms 6744 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 8028 KB Output is correct
2 Correct 8 ms 9008 KB Output is correct
3 Correct 26 ms 12124 KB Output is correct
4 Correct 25 ms 11500 KB Output is correct
5 Correct 47 ms 16212 KB Output is correct
6 Correct 46 ms 16208 KB Output is correct
7 Correct 45 ms 16212 KB Output is correct
8 Correct 52 ms 16216 KB Output is correct
9 Correct 118 ms 29392 KB Output is correct
10 Correct 145 ms 20304 KB Output is correct
11 Correct 287 ms 40168 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 432 KB Output is correct
18 Correct 8 ms 8028 KB Output is correct
19 Correct 7 ms 8028 KB Output is correct
20 Correct 8 ms 9052 KB Output is correct
21 Correct 21 ms 19060 KB Output is correct
22 Incorrect 174 ms 31356 KB 1st lines differ - on the 1st token, expected: '45561826463480', found: '45468849597150'
23 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 12536 KB Output is correct
2 Correct 47 ms 13880 KB Output is correct
3 Correct 7 ms 8028 KB Output is correct
4 Correct 6 ms 8268 KB Output is correct
5 Correct 142 ms 29536 KB Output is correct
6 Correct 143 ms 33376 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 99 ms 26432 KB Output is correct
9 Correct 124 ms 31344 KB Output is correct
10 Correct 36 ms 14128 KB Output is correct
11 Correct 44 ms 15668 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 7 ms 8116 KB Output is correct
17 Correct 8 ms 8276 KB Output is correct
18 Correct 51 ms 18600 KB Output is correct
19 Correct 62 ms 20760 KB Output is correct
20 Correct 44 ms 17512 KB Output is correct
21 Correct 59 ms 18968 KB Output is correct
22 Correct 47 ms 17548 KB Output is correct
23 Correct 51 ms 18872 KB Output is correct
24 Correct 6 ms 8028 KB Output is correct
25 Correct 8 ms 9008 KB Output is correct
26 Correct 26 ms 12124 KB Output is correct
27 Correct 25 ms 11500 KB Output is correct
28 Correct 47 ms 16212 KB Output is correct
29 Correct 46 ms 16208 KB Output is correct
30 Correct 45 ms 16212 KB Output is correct
31 Correct 52 ms 16216 KB Output is correct
32 Correct 1 ms 344 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 344 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 2 ms 348 KB Output is correct
41 Correct 14 ms 856 KB Output is correct
42 Correct 3 ms 344 KB Output is correct
43 Correct 4 ms 652 KB Output is correct
44 Correct 1 ms 604 KB Output is correct
45 Correct 3 ms 604 KB Output is correct
46 Correct 1 ms 344 KB Output is correct
47 Correct 85 ms 604 KB Output is correct
48 Execution timed out 1038 ms 6744 KB Time limit exceeded
49 Halted 0 ms 0 KB -