Submission #723443

#	Time	Username	Problem	Language	Result	Execution time	Memory
723443		anton	Measures (CEOI22_measures)	C++17	24 / 100	1553 ms	10628 KiB

Main

#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 (stderr)

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 / 10
• Subtask 2: 14 / 14
• Subtask 3: 0 / 35
• Subtask 4: 0 / 41