oj.uz

Submission #625873

# Submission time Handle Problem Language Result Execution time Memory
625873 2022-08-10T23:58:27 Z xynex Catfish Farm (IOI22_fish) C++17
100 / 100
 145 ms 18288 KB 
/**
  * Author: Tenjin
  * Created: 11.08.2022 05:09
  * Why am I so stupid? :c
  * Slishkom slab
**/

#include <bits/stdc++.h>
#include "fish.h"
// #pragma GCC optimize("inline")
// #pragma GCC optimize("-fgcse,-fgcse-lm")
// #pragma GCC optimize("-ftree-pre,-ftree-vrp")
// #pragma GCC optimize("-ffast-math")
// #pragma GCC optimize("-fipa-sra")
// #pragma GCC optimize("-fpeephole2")
// #pragma GCC optimize("-fsched-spec")
// #pragma GCC optimize("Ofast,no-stack-protector")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
// #pragma GCC optimize("unroll-loops")

using namespace std;

#define ll long long
#define dl double long
#define ull unsigned long long
#define pr pair
#define vt vector
#define ff first
#define ss second
#define mp make_pair
#define sz(a) (int)a.size()
#define pb push_back
#define pf push_front
#define popB pop_back
#define popF pop_front
#define bit_count __builtin_popcount
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sp(x) fixed << setprecision(x)

template<typename T> T get_rand(T l, T r) {
  random_device rd;
  mt19937 gen(rd());
  return uniform_int_distribution<T>(l, r)(gen);
}
template<typename T> T lcm(T a, T b) { return a * (b / __gcd(a, b)); }

template<class A> void read(vt<A>& v);
template<class A, size_t S> void read(array<A, S>& a);
template<class T> void read(T& x) { cin >> x; }
void read(double& d) { string t; read(t); d = stod(t); }
void read(long double& d) { string t; read(t); d = stold(t); }
template<class H, class... T> void read(H& h, T&... t) { read(h); read(t...); }
template<class A> void read(vt<A>& x) { for (auto& a : x) read(a); }
template<class A, size_t S> void read(array<A, S>& x) { for (auto& a : x) read(a); }

string to_string(char c) { return string(1, c); }
string to_string(bool b) { return b ? "true" : "false"; }
string to_string(const char* s) { return string(s); }
string to_string(string s) { return s; }
string to_string(vt<bool> v) { string res; for (int i = 0; i < sz(v); ++i) res += char('0' + v[i]); return res; }
template<size_t S> string to_string(bitset<S> b) { string res; for (int i = 0; i < S; ++i) res += char('0' + b[i]); return res; }
template<class T> string to_string(T v) { bool f = 1; string res; for (auto x : v) { if (!f) res += ' '; f = 0; res += to_string(x); } return res; }

template<class A> void write(A x) { cout << to_string(x); }
template<class H, class... T> void write(const H& h, const T&... t) { write(h); write(t...); }

void print() { write("\n"); }
template<class H, class... T> void print(const H& h, const T&... t) { write(h); if (sizeof...(t)) write(' '); print(t...); }

void freop(string s) {
  freopen((s + ".in").c_str(), "r", stdin);
  freopen((s + ".out").c_str(), "w", stdout);
}

const int MOD = 1e9 + 7;
const int N = 3e6 + 5;
const ll INF = 1e18;
const int M = 3e3 + 5;
const dl pi = acos(-1);
const dl eps = 1e-12;
const int sq = 700;

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};
/* ll vs int*/

ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
  vt<vt<pr<int, ll> >> fishes(n);
  for(int i = 0; i < m; ++i) {
    fishes[x[i]].pb({y[i], w[i]});
  }
  vt<ll> pref(n, -INF);
  vt<ll> last1, last2;
  for(int x = 0; x < n; ++x) {
    sort(all(fishes[x]));
    vt<ll> cur1(sz(fishes[x]), -INF);
    ll mx1 = -INF, lastmx1 = -INF;
    if(x > 0) {
      int pos = sz(fishes[x - 1]) - 1;
      for(int i = sz(fishes[x]) - 1; i >= 0; --i) {
        int Y = fishes[x][i].ff;
        ll W = fishes[x][i].ss;
        cur1[i] = max(0ll, mx1) + W;
        if(x > 1) {
          cur1[i] = max(cur1[i], pref[x - 2] + W);
        }
        while(pos >= 0) {
          if(fishes[x - 1][pos].ff <= Y) break;
          lastmx1 = max(lastmx1, last1[pos]);
          pos--;
        }
        cur1[i] = max(cur1[i], lastmx1 + W);
        mx1 = max(mx1, cur1[i]);
      }
    }
    if(!last1.empty()) lastmx1 = *max_element(all(last1));
    swap(last1, cur1);
    vt<ll> cur2(sz(fishes[x]), -INF);
    ll mx2 = -INF, lastmx2 = -INF;
    if(x < n - 1) {
      int pos = 0;
      for(int i = 0; i < sz(fishes[x]); ++i) {
        int Y = fishes[x][i].ff;
        ll W = fishes[x][i].ss;
        cur2[i] = max(0ll, mx2) + W;
        cur2[i] = max(cur2[i], lastmx1 + W);
        if(x > 1) {
          cur2[i] = max(cur2[i], pref[x - 2] + W);
        }
        if(x) {
          while(pos < sz(fishes[x - 1])) {
            if(fishes[x - 1][pos].ff >= Y) break;
            lastmx2 = max(lastmx2, last2[pos]);
            pos++;
          }
        }
        cur2[i] = max(cur2[i], lastmx2 + W);
        mx2 = max(mx2, cur2[i]);
      }
    }
    swap(last2, cur2);
    if(x)  pref[x] = max({pref[x - 1], mx1, mx2});
    else pref[x] = max({mx1, mx2});
  }
  return pref[n - 1];
}

Compilation message

fish.cpp: In function 'void freop(std::string)':
fish.cpp:72:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |   freopen((s + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:73:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |   freopen((s + ".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 7452 KB Output is correct
2 Correct 51 ms 8884 KB Output is correct
3 Correct 3 ms 3412 KB Output is correct
4 Correct 3 ms 3412 KB Output is correct
5 Correct 123 ms 17124 KB Output is correct
6 Correct 126 ms 18124 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 63 ms 11976 KB Output is correct
3 Correct 78 ms 14416 KB Output is correct
4 Correct 31 ms 7508 KB Output is correct
5 Correct 39 ms 8888 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 3 ms 3388 KB Output is correct
11 Correct 2 ms 3412 KB Output is correct
12 Correct 33 ms 7520 KB Output is correct
13 Correct 40 ms 8900 KB Output is correct
14 Correct 33 ms 7556 KB Output is correct
15 Correct 37 ms 8388 KB Output is correct
16 Correct 35 ms 7480 KB Output is correct
17 Correct 35 ms 8240 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3412 KB Output is correct
2 Correct 3 ms 3412 KB Output is correct
3 Correct 24 ms 6064 KB Output is correct
4 Correct 18 ms 5332 KB Output is correct
5 Correct 45 ms 8900 KB Output is correct
6 Correct 43 ms 9012 KB Output is correct
7 Correct 43 ms 8780 KB Output is correct
8 Correct 60 ms 8780 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 16 ms 2252 KB Output is correct
18 Correct 17 ms 2888 KB Output is correct
19 Correct 16 ms 2772 KB Output is correct
20 Correct 16 ms 2628 KB Output is correct
21 Correct 16 ms 2644 KB Output is correct
22 Correct 31 ms 5088 KB Output is correct
23 Correct 4 ms 724 KB Output is correct
24 Correct 12 ms 1712 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 3 ms 648 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 16 ms 2252 KB Output is correct
18 Correct 17 ms 2888 KB Output is correct
19 Correct 16 ms 2772 KB Output is correct
20 Correct 16 ms 2628 KB Output is correct
21 Correct 16 ms 2644 KB Output is correct
22 Correct 31 ms 5088 KB Output is correct
23 Correct 4 ms 724 KB Output is correct
24 Correct 12 ms 1712 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 3 ms 648 KB Output is correct
27 Correct 2 ms 468 KB Output is correct
28 Correct 75 ms 11080 KB Output is correct
29 Correct 126 ms 14668 KB Output is correct
30 Correct 118 ms 14052 KB Output is correct
31 Correct 113 ms 14048 KB Output is correct
32 Correct 107 ms 15972 KB Output is correct
33 Correct 110 ms 14128 KB Output is correct
34 Correct 112 ms 14108 KB Output is correct
35 Correct 50 ms 6220 KB Output is correct
36 Correct 108 ms 15932 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3412 KB Output is correct
2 Correct 3 ms 3412 KB Output is correct
3 Correct 24 ms 6064 KB Output is correct
4 Correct 18 ms 5332 KB Output is correct
5 Correct 45 ms 8900 KB Output is correct
6 Correct 43 ms 9012 KB Output is correct
7 Correct 43 ms 8780 KB Output is correct
8 Correct 60 ms 8780 KB Output is correct
9 Correct 55 ms 8900 KB Output is correct
10 Correct 41 ms 6732 KB Output is correct
11 Correct 90 ms 13260 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 3 ms 3412 KB Output is correct
19 Correct 3 ms 3412 KB Output is correct
20 Correct 3 ms 3412 KB Output is correct
21 Correct 2 ms 3412 KB Output is correct
22 Correct 57 ms 8600 KB Output is correct
23 Correct 90 ms 13272 KB Output is correct
24 Correct 91 ms 13268 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 7452 KB Output is correct
2 Correct 51 ms 8884 KB Output is correct
3 Correct 3 ms 3412 KB Output is correct
4 Correct 3 ms 3412 KB Output is correct
5 Correct 123 ms 17124 KB Output is correct
6 Correct 126 ms 18124 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 63 ms 11976 KB Output is correct
9 Correct 78 ms 14416 KB Output is correct
10 Correct 31 ms 7508 KB Output is correct
11 Correct 39 ms 8888 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 3 ms 3388 KB Output is correct
17 Correct 2 ms 3412 KB Output is correct
18 Correct 33 ms 7520 KB Output is correct
19 Correct 40 ms 8900 KB Output is correct
20 Correct 33 ms 7556 KB Output is correct
21 Correct 37 ms 8388 KB Output is correct
22 Correct 35 ms 7480 KB Output is correct
23 Correct 35 ms 8240 KB Output is correct
24 Correct 3 ms 3412 KB Output is correct
25 Correct 3 ms 3412 KB Output is correct
26 Correct 24 ms 6064 KB Output is correct
27 Correct 18 ms 5332 KB Output is correct
28 Correct 45 ms 8900 KB Output is correct
29 Correct 43 ms 9012 KB Output is correct
30 Correct 43 ms 8780 KB Output is correct
31 Correct 60 ms 8780 KB Output is correct
32 Correct 1 ms 212 KB Output is correct
33 Correct 0 ms 212 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 0 ms 212 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 0 ms 212 KB Output is correct
38 Correct 0 ms 212 KB Output is correct
39 Correct 0 ms 212 KB Output is correct
40 Correct 0 ms 212 KB Output is correct
41 Correct 1 ms 340 KB Output is correct
42 Correct 1 ms 340 KB Output is correct
43 Correct 1 ms 340 KB Output is correct
44 Correct 1 ms 212 KB Output is correct
45 Correct 1 ms 340 KB Output is correct
46 Correct 0 ms 212 KB Output is correct
47 Correct 1 ms 340 KB Output is correct
48 Correct 16 ms 2252 KB Output is correct
49 Correct 17 ms 2888 KB Output is correct
50 Correct 16 ms 2772 KB Output is correct
51 Correct 16 ms 2628 KB Output is correct
52 Correct 16 ms 2644 KB Output is correct
53 Correct 31 ms 5088 KB Output is correct
54 Correct 4 ms 724 KB Output is correct
55 Correct 12 ms 1712 KB Output is correct
56 Correct 1 ms 340 KB Output is correct
57 Correct 3 ms 648 KB Output is correct
58 Correct 2 ms 468 KB Output is correct
59 Correct 75 ms 11080 KB Output is correct
60 Correct 126 ms 14668 KB Output is correct
61 Correct 118 ms 14052 KB Output is correct
62 Correct 113 ms 14048 KB Output is correct
63 Correct 107 ms 15972 KB Output is correct
64 Correct 110 ms 14128 KB Output is correct
65 Correct 112 ms 14108 KB Output is correct
66 Correct 50 ms 6220 KB Output is correct
67 Correct 108 ms 15932 KB Output is correct
68 Correct 55 ms 8900 KB Output is correct
69 Correct 41 ms 6732 KB Output is correct
70 Correct 90 ms 13260 KB Output is correct
71 Correct 0 ms 212 KB Output is correct
72 Correct 0 ms 212 KB Output is correct
73 Correct 1 ms 212 KB Output is correct
74 Correct 0 ms 212 KB Output is correct
75 Correct 0 ms 212 KB Output is correct
76 Correct 0 ms 212 KB Output is correct
77 Correct 3 ms 3412 KB Output is correct
78 Correct 3 ms 3412 KB Output is correct
79 Correct 3 ms 3412 KB Output is correct
80 Correct 2 ms 3412 KB Output is correct
81 Correct 57 ms 8600 KB Output is correct
82 Correct 90 ms 13272 KB Output is correct
83 Correct 91 ms 13268 KB Output is correct
84 Correct 135 ms 16056 KB Output is correct
85 Correct 127 ms 16148 KB Output is correct
86 Correct 145 ms 17736 KB Output is correct
87 Correct 143 ms 18276 KB Output is correct
88 Correct 0 ms 212 KB Output is correct
89 Correct 144 ms 18272 KB Output is correct
90 Correct 128 ms 18288 KB Output is correct
91 Correct 119 ms 18148 KB Output is correct