oj.uz

Submission #723437

# Submission time Handle Problem Language Result Execution time Memory
723437 2023-04-13T19:50:54 Z anton Measures (CEOI22_measures) C++17
0 / 100
 1500 ms 1692 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;
    int first = *s.begin();

    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);

        cout<<((double)my_score(s, d))/2.0;
        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++){
      |                          ~^~~~~~~~~
Main.cpp: In function 'long long int my_score(std::multiset<long long int>&, long long int)':
Main.cpp:30:9: warning: unused variable 'first' [-Wunused-variable]
   30 |     int first = *s.begin();
      |         ^~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1571 ms 1692 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 1571 ms 1692 KB Time limit exceeded
2 Halted 0 ms 0 KB -