oj.uz

Submission #723443

# Submission time Handle Problem Language Result Execution time Memory
723443 2023-04-13T19:58:53 Z anton Measures (CEOI22_measures) C++17
24 / 100
 1500 ms 10628 KB 
#include<bits/stdc++.h>

using namespace std;

mt19937 rng(42);
#define int long long

int score(multiset<int>& s, int d){
    vector<int> v;

    for(auto e: s){
        v.push_back(e);
    }

    int score = 0;

    for(int i = 0; i<v.size(); i++){
        for(int j = i+1; j<v.size(); j++){
            score = max(score, (j-i)*d - (v[j]-v[i]));
        }
    }

    return score;
}

int my_score(multiset<int>& s, int d){
    int delta = 0;
    int score = 0;
    int rank = 0;

    for(auto e: s){
        if(delta + rank*d < e){
            delta = e -rank*d;
        }
        //cout<<"delta "<<delta<<endl;
        score = max(score, rank*d + delta - e);
        rank++;
    }

    return score;
}

void test(){
    multiset<int> s;

    int d= rng();

    for(int i = 0; i<100; i++){
        s.insert(rng()%1000 + 1000LL*1000LL*1000LL*1000LL*1000LL);
    }
    
    int s1 = my_score(s, d);
    int s2 = score(s, d);
    if(s1!=s2){
        cout<<"example: "<<d<<endl;
        /*for(auto e: s){
            cout<<e<<endl;
        }
        cout<<s1<<" "<<s2<<endl;*/
    }

}
signed main(){
    /*srand(time(NULL));
    

    for(int i = 0; i<100*1000; i++){
        test();
    }*/

    int n, m, d;
    cin>>n>>m>>d;

    multiset<int> s;

    int a;

    for(int i = 0; i<n; i++){
        cin>>a;
        s.insert(a);
    }

    int b;
    for(int i = 0; i<m; i++){
        cin>>b;
        s.insert(b);

        int s1 = my_score(s, d);
        cout<<s1/2;
        if(s1%2==1){
            cout<<".5";
        }
        if(i<m-1){
            cout<<" ";
        }
    }
    cout<<endl;
}

Compilation message

Main.cpp: In function 'long long int score(std::multiset<long long int>&, long long int)':
Main.cpp:17:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int i = 0; i<v.size(); i++){
      |                    ~^~~~~~~~~
Main.cpp:18:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         for(int j = i+1; j<v.size(); j++){
      |                          ~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 316 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 316 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 380 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 316 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 316 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 380 KB Output is correct
9 Correct 290 ms 10300 KB Output is correct
10 Correct 162 ms 10520 KB Output is correct
11 Correct 129 ms 10572 KB Output is correct
12 Correct 145 ms 10628 KB Output is correct
13 Correct 115 ms 10608 KB Output is correct
14 Correct 140 ms 10588 KB Output is correct
15 Correct 301 ms 10480 KB Output is correct
16 Correct 129 ms 10524 KB Output is correct

Subtask #3
0 / 35.0

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

Subtask #4
0 / 41.0

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