/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 540.0 KiB
#2 Wrong Answer 37ms 836.0 KiB
#3 Wrong Answer 56ms 736.0 KiB

Code

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld  long double
#define ull unsigned long long
#define PI acos(-1.0)
#define vi vector<ll>
#define pii pair<ll,ll>
#define vii vector<pii>
#define rev_str(str) reverse(str.begin(),str.end());
#define print(v) for(auto i:v) cout<<i<<" ";cout<<endl;
#define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define rep(i,a,b) for(ll i =a ;i<b;i++)
#define per(i,b,a) for(ll i=b;i>=a;i--)
#define all(a)  (a.begin(),a.end())
#define srt(a) sort(a.begin(),a.end())
#define rsrt(a) sort(a.rbegin(),a.rend())
bool sortByValue(const pair<int,int>& a,const pair<int,int>& b){
    return a.second > b.second;
}
const ll N=10e5+5;

ll gcd(ll a,ll b){
    return b == 0 ? a : gcd(b, a%b);
}

ll lcm(ll a,ll b){
    return (a / gcd(a, b)) * b;
}


void solve(){
    ll n,m;cin>>n>>m;
    vi p(n),q(n+1);
    map<ll,ll>f;
    rep(i,0,n){
        cin>>p[i];
        f[p[i]]++;
        q[i+1]=q[i]+p[i];
    }
    //print(q);
    if (n == m){
        ll sum = accumulate(p.begin(), p.end(), 0LL);
        cout << sum << endl;
        return;
    }
    
    vi s;
    s=p;
    map<ll,ll>mpp;
    srt(s);
    ll mn = 1e14;
    ll prev,right;
    //print(s);
    ll l=0,r=l+3;
    rep(i,0,n-m+1){
        l = i;
        r = l+m;
        ll sum  = q[r]-q[l];
        if(sum<mn){ 
            mn = sum;
            prev = l;
            right = r;
        }
    }
    //cout << mn << ' ' << prev << ' ' << right << endl;
    vector <ll> main, sec;
    for (int i = prev; i < right; i++){
        main.push_back(p[i]);
    }

    if(prev == 0){
        for (int i = right; i < n; i++){
            sec.push_back(p[i]);
        }
    }
    else{
        for (int i = 0; i < prev; i++){
            sec.push_back(p[i]);
        }
        for (int i = right; i < n; i++){
            sec.push_back(p[i]);
        }
    }

    sort(main.begin(), main.end());
    sort(sec.begin(), sec.end());

    // for (auto i : main) cout << i << ' ';
    // cout << endl;
    // for (auto i : sec) cout << i << ' ';
    // cout << endl;
    // cout << endl;
    ll sum = 0;
    //cout << main[main.size() - 1] << endl;
    if (main[main.size() - 1] > sec[0]){
        sum = accumulate(main.begin(), main.end(), 0LL);
        sum -= main[main.size() - 1];
        sum += sec[0];
    }
    else{
        sum = accumulate(main.begin(), main.end(), 0LL);
    }

    cout << sum << endl;
}

int main(){
    fast;
    ll t=1;cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Information

Submit By
Type
Submission
Problem
P1149 Swap and Minimize
Contest
LU IUJPC : Sylhet Division 2024
Language
C++17 (G++ 13.2.0)
Submit At
2024-12-09 06:58:01
Judged At
2024-12-09 06:58:01
Judged By
Score
1
Total Time
56ms
Peak Memory
836.0 KiB