oj.uz

Submission #1059993

# Submission time Handle Problem Language Result Execution time Memory
1059993 2024-08-15T09:56:24 Z dozer Closing Time (IOI23_closing) C++17
0 / 100
 1000 ms 11608 KB 
#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
#define sp " " 
#define endl "\n"
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define LL node * 2
#define RR node * 2 + 1
#define ll long long

const int modulo = 1e9 + 7;
const ll INF = 2e18 + 7;


int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W)
{
    vector<ll> lft, rgt;
    lft.pb(0), rgt.pb(0);
    ll sum = 0;
    for (int i = X - 1; i >= 0; i--){
        sum += W[i];
        lft.pb(lft.back() + sum);
    }

    sum = 0;
    for (int i = Y + 1; i < N; i++){
        sum += W[i - 1];
        rgt.pb(rgt.back() + sum);
    }

    int ans = 0;

    //todo : no one can reach the other
    {
        vector<ll> merge(2 * N + 2, INF);
        for (int i = 0; i < lft.size(); i++){
            for (int j = 0; j < rgt.size(); j++)
                merge[i + j] = min(merge[i + j], lft[i] + rgt[j]);
        }
        
        vector<int> cost(N, 0);
        ll total = 0;
        ll GH = 0;
        for (int i = X; i <= Y; i++){
            if (i > X) {
                GH += W[i - 1];
                cost[i] = GH;
                total += cost[i];;
            }
            ll sum = total;
            ll GH2 = 0;
            for (int j = Y; j >= X; j--){
                if (j < Y) {
                    GH2 += W[j];
                    sum += max((ll)0, GH2 - cost[j]);
                }
                int pos = upper_bound(merge.begin(), merge.end(), K - sum) - merge.begin();
                if (sum <= K) ans = max(ans, pos + i - X + Y - j + 1);
            }
        }
    }

    //todo : X can reach Y

    {
        vector<ll> merge(2 * N + 2, INF);
        for (int i = 0; i < lft.size(); i++){
            for (int j = 0; j < rgt.size(); j++)
                merge[i + j] = min(merge[i + j * 2], lft[i] + rgt[j]);
        }

        
        vector<int> cost(N, 0);
        ll total = 0, GH = 0;;
        for (int i = X + 1; i <= Y; i++){
             GH += W[i - 1];
            cost[i] = GH;
            total += cost[i];
        }

        ll GH2 = 0;
        for (int i = Y; i >= X; i--){
            if (i < Y) {
                GH2 += W[i];
                total += max((ll)0, GH2 - cost[i]);
            }
            int pos = upper_bound(merge.begin(), merge.end(), K - total) - merge.begin();
            if (total <= K) ans = max(ans, pos + Y - X + Y - i + 1);
        }
    }


    //todo : Y can reach X

    {
        vector<ll> merge(2 * N + 2, INF);
        for (int i = 0; i < lft.size(); i++){
            for (int j = 0; j < rgt.size(); j++)
                merge[i + j] = min(merge[i * 2 + j], lft[i] + rgt[j]);
        }

        
        vector<int> cost(N, 0);
        ll total = 0, GH = 0;
        for (int i = Y - 1; i >= X; i--){
            GH += W[i];
            cost[i] = GH;
            total += cost[i];
        }

        ll GH2 = 0;
        for (int i = X; i <= Y; i++){
            if (i > X) {
                GH2 += W[i - 1];
                total += max((ll)0, GH2 - cost[i - 1]);
            }
            int pos = upper_bound(merge.begin(), merge.end(), K - total) - merge.begin();
            if (total <= K) ans = max(ans, pos + Y - X + i - X + 1);
        }
    }


    //todo : both can reach each other

    {
        vector<ll> merge(2 * N + 2, INF);
        for (int i = 0; i < lft.size(); i++){
            for (int j = 0; j < rgt.size(); j++)
                merge[i + j] = min(merge[i * 2 + j * 2], lft[i] + rgt[j]);
        }

        
        vector<int> cost(N, 0);
        ll total = 0, GH = 0;
        for (int i = Y - 1; i >= X; i--){
            GH += W[i];
            cost[i] = GH;
            total += cost[i];
        }

        ll GH2 = 0;
        for (int i = X; i <= Y; i++){
            if (i > X) {
                GH2 += W[i - 1];
                total += max((ll)0, GH2 - cost[i - 1]);
            }
        }
        int pos = upper_bound(merge.begin(), merge.end(), K - total) - merge.begin();
        if (total <= K) ans = max(ans, pos + Y - X + Y - X + 1);
    }

    return ans;
}

/*
int main()
{
    fileio();
    int Q;
    assert(1 == scanf("%d", &Q));

    std::vector<int> N(Q), X(Q), Y(Q);
    std::vector<long long> K(Q);
    std::vector<std::vector<int>> U(Q), V(Q), W(Q);

    for (int q = 0; q < Q; q++)
    {
        assert(4 == scanf("%d %d %d %lld", &N[q], &X[q], &Y[q], &K[q]));

        U[q].resize(N[q] - 1);
        V[q].resize(N[q] - 1);
        W[q].resize(N[q] - 1);
        for (int i = 0; i < N[q] - 1; ++i)
        {
            assert(3 == scanf("%d %d %d", &U[q][i], &V[q][i], &W[q][i]));
        }
    }
    fclose(stdin);

    std::vector<int> result(Q);
    for (int q = 0; q < Q; q++)
    {
        result[q] = max_score(N[q], X[q], Y[q], K[q], U[q], V[q], W[q]);
    }

    for (int q = 0; q < Q; q++)
    {
        printf("%d\n", result[q]);
    }
    fclose(stdout);

    return 0;
}
*/

Compilation message

closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:41:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for (int i = 0; i < lft.size(); i++){
      |                         ~~^~~~~~~~~~~~
closing.cpp:42:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |             for (int j = 0; j < rgt.size(); j++)
      |                             ~~^~~~~~~~~~~~
closing.cpp:72:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for (int i = 0; i < lft.size(); i++){
      |                         ~~^~~~~~~~~~~~
closing.cpp:73:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |             for (int j = 0; j < rgt.size(); j++)
      |                             ~~^~~~~~~~~~~~
closing.cpp:102:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         for (int i = 0; i < lft.size(); i++){
      |                         ~~^~~~~~~~~~~~
closing.cpp:103:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |             for (int j = 0; j < rgt.size(); j++)
      |                             ~~^~~~~~~~~~~~
closing.cpp:132:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |         for (int i = 0; i < lft.size(); i++){
      |                         ~~^~~~~~~~~~~~
closing.cpp:133:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |             for (int j = 0; j < rgt.size(); j++)
      |                             ~~^~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1002 ms 11608 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 9.0

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

Subtask #3
0.0 / 12.0

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

Subtask #4
0.0 / 14.0

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

Subtask #5
0.0 / 9.0

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

Subtask #6
0.0 / 11.0

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

Subtask #7
0.0 / 10.0

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

Subtask #8
0.0 / 10.0

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

Subtask #9
0.0 / 17.0

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