oj.uz

Submission #1113235

# Submission time Handle Problem Language Result Execution time Memory
1113235 2024-11-16T07:24:29 Z ljtunas Topical (NOI23_topical) C++14
61 / 100
 376 ms 226628 KB 
// author : anhtun_hi , nqg
#include <bits/stdc++.h>
#define ll long long
#define ii pair<ll, ll>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define reset(h, v)    memset(h, v, sizeof h)
#define Forv(i, a)     for(auto& i : a)
#define For(i, a, b)   for(int i = a; i <= b; ++i)
#define Ford(i, a, b)  for(int i = a; i >= b; --i)
#define c_bit(i)     __builtin_popcountll(i)
#define Bit(mask, i)    ((mask >> i) & 1LL)
#define onbit(mask, i)  ((mask) bitor (1LL << i))
#define offbit(mask, i) ((mask) &~ (1LL << i))
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
using namespace std;
namespace std {
    template <typename T, int D>
    struct _vector : public vector <_vector <T, D - 1>> {
        static_assert(D >= 1, "Dimension must be positive!");
        template <typename... Args>
        _vector(int n = 0, Args... args) : vector <_vector <T, D - 1>> (n, _vector <T, D - 1> (args...)) {}
    };
    template <typename T> struct _vector <T, 1> : public vector <T> {
        _vector(int n = 0, const T& val = T()) : vector <T> (n, val) {}
    };
    template <class A, class B> bool minimize(A &a, B b){return a > b ? a = b, true : false;}
    template <class A, class B> bool maximize(A &a, B b){return a < b ? a = b, true : false;}
}
const int dx[] = {0, 0, +1, -1}, dy[] = {-1, +1, 0, 0}, LOG = 20, base = 311, inf = 1e9 + 5;
const int MAXN = 1e6 + 5;
const  ll  mod = 1e9 + 7;
const  ll   oo = 1e18;

//#define int long long

int n, k;
vector<vector<ll>> r, u;

namespace sub1{
    bool check(){ return n == 1; }
    void Solve(){
        int ans = 1;
        For(i, 1, k) if(r[1][i] > 0) ans &= 0;
        cout << (ans == 1) ? 1 : 0 << '\n';
    }
}

namespace sub2{
    bool check() { return n <= 100 && k <= 100; }
    bool del[MAXN];
    void Solve(){
        vector<ll> rate(k + 1);
        int ans = 0;
        while (true){
            bool on = false;
            For(i, 1, n) if(!del[i]){
                bool ok = true;
                For(j, 1, k) ok &= (rate[j] >= r[i][j]);
                if(ok) {
                    ++ans;
                    For(j, 1, k) rate[j] += u[i][j];
                    on = true;
                    del[i] = true;
                }
            }
            if (!on) break;
        }
        cout << ans << '\n';
    }
}

namespace sub3{
    bool check() {return k == 1;}
    ii a[MAXN];
    void Solve(){
         For(i, 1, n) a[i] = {r[i][1], u[i][1]};
         sort(a + 1, a + n + 1);
         int ans = 0; ll sum = 0;
         For(i, 1, n) {
            if (sum >= a[i].fi) ++ ans, sum += a[i].se;
            else break;
         }
         cout << ans << '\n';
    }
}

namespace sub4{
    vector<ii> vec[MAXN];
    ll s[MAXN];int cnt[MAXN], id[MAXN];
    void Solve(){
        For(i, 1, n) For(j, 1, k){
            vec[j].push_back({r[i][j], i});
        }
        For(i, 1, n) sort(all(vec[i]));
        int ans = 0;
        For(i, 1, k) fill(id + 1, id + n + 1, 1);
        while (true){
            vector<int> List;
            For(i, 1, k){
                while(id[i] <= n && s[i] >= vec[i][id[i] - 1].fi){
                    ++cnt[vec[i][id[i] - 1].se];
                    if(cnt[vec[i][id[i] - 1].se] == k) List.push_back(vec[i][id[i] - 1].se);
//                    cerr << vec[i][id[i] - 1].se << ' ' << cnt[vec[i][id[i] - 1].se] << '\n';
                    ++id[i];
                }
            }
            if (List.empty()) break;
            Forv(i, List) {
                ++ans;
                For(j, 1, k) s[j] += u[i][j];
            }
        }
        cout << ans << '\n';
    }
}

void Solve() {
    cin >> n >> k;
    r.resize(n + 5, vector<ll>(k + 5));
    u.resize(n + 5, vector<ll>(k + 5));
    For(i, 1, n) For(j, 1, k) cin >> r[i][j];
    For(i, 1, n) For(j, 1, k) cin >> u[i][j];
    if(sub1::check()) sub1::Solve();
    else if (sub3::check()) sub3::Solve();
    else if (sub2::check()) sub2::Solve();
    else sub4::Solve();
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    if(fopen("NOI23_topical.inp", "r")) {
        freopen("NOI23_topical.inp", "r", stdin);
        freopen("NOI23_topical.out", "w", stdout);
    }

    int t = 1;
//    cin >> t;
    while(t --) Solve();

    return 0;
}

Compilation message

Main.cpp: In function 'void sub1::Solve()':
Main.cpp:46:43: warning: second operand of conditional expression has no effect [-Wunused-value]
   46 |         cout << (ans == 1) ? 1 : 0 << '\n';
      |                                           ^
Main.cpp:46:36: warning: third operand of conditional expression has no effect [-Wunused-value]
   46 |         cout << (ans == 1) ? 1 : 0 << '\n';
      |                                  ~~^~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:134:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |         freopen("NOI23_topical.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:135:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |         freopen("NOI23_topical.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23888 KB Output is correct
2 Correct 18 ms 23888 KB Output is correct
3 Correct 18 ms 24912 KB Output is correct
4 Correct 190 ms 137140 KB Output is correct
5 Correct 202 ms 137192 KB Output is correct
6 Correct 212 ms 137144 KB Output is correct
7 Correct 202 ms 131504 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23888 KB Output is correct
2 Correct 18 ms 23972 KB Output is correct
3 Correct 16 ms 23772 KB Output is correct
4 Correct 17 ms 23888 KB Output is correct
5 Correct 17 ms 23888 KB Output is correct
6 Correct 17 ms 23888 KB Output is correct
7 Correct 20 ms 24144 KB Output is correct
8 Correct 19 ms 24144 KB Output is correct
9 Correct 19 ms 24144 KB Output is correct
10 Correct 16 ms 24144 KB Output is correct
11 Correct 17 ms 24144 KB Output is correct
12 Correct 17 ms 24320 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23888 KB Output is correct
2 Correct 15 ms 23976 KB Output is correct
3 Correct 18 ms 25936 KB Output is correct
4 Correct 49 ms 44024 KB Output is correct
5 Correct 53 ms 43848 KB Output is correct
6 Correct 376 ms 226628 KB Output is correct
7 Correct 366 ms 225096 KB Output is correct
8 Correct 366 ms 226616 KB Output is correct
9 Correct 359 ms 225252 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23888 KB Output is correct
2 Correct 18 ms 23888 KB Output is correct
3 Correct 18 ms 24912 KB Output is correct
4 Correct 190 ms 137140 KB Output is correct
5 Correct 202 ms 137192 KB Output is correct
6 Correct 212 ms 137144 KB Output is correct
7 Correct 202 ms 131504 KB Output is correct
8 Correct 17 ms 23888 KB Output is correct
9 Correct 18 ms 23972 KB Output is correct
10 Correct 16 ms 23772 KB Output is correct
11 Correct 17 ms 23888 KB Output is correct
12 Correct 17 ms 23888 KB Output is correct
13 Correct 17 ms 23888 KB Output is correct
14 Correct 20 ms 24144 KB Output is correct
15 Correct 19 ms 24144 KB Output is correct
16 Correct 19 ms 24144 KB Output is correct
17 Correct 16 ms 24144 KB Output is correct
18 Correct 17 ms 24144 KB Output is correct
19 Correct 17 ms 24320 KB Output is correct
20 Correct 15 ms 23888 KB Output is correct
21 Correct 15 ms 23976 KB Output is correct
22 Correct 18 ms 25936 KB Output is correct
23 Correct 49 ms 44024 KB Output is correct
24 Correct 53 ms 43848 KB Output is correct
25 Correct 376 ms 226628 KB Output is correct
26 Correct 366 ms 225096 KB Output is correct
27 Correct 366 ms 226616 KB Output is correct
28 Correct 359 ms 225252 KB Output is correct
29 Incorrect 194 ms 78672 KB Output isn't correct
30 Halted 0 ms 0 KB -