/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 540.0 KiB
#2 Wrong Answer 47ms 568.0 KiB
#3 Wrong Answer 79ms 576.0 KiB

Code

/*************************************************  Bismillahir Rahmanir Rahim  *************************************************/


/*  You can't do anything until you try  */
#include<bits/stdc++.h>
using namespace std;


/*=====================================*/
#define     Checkmate                                  return 0
#define     ll                                         long long
#define     newl                                       '\n'
#define     spc                                        ' '
#define     Start                                      ios_base::sync_with_stdio(false); cin.tie(0);
#define     Hunting                                    if(fopen("inputf.in", "r")) 
#define     Bugs                                       {freopen("inputf.in", "r", stdin);  freopen("outputf.in", "w", stdout);}

#define     YES                                        cout<<"YES\n"
#define     NO                                         cout<<"NO\n"
#define     basic_if_else(x)                           x?YES:NO


#define     allEmt(v)                                  v.begin(), v.end()
#define     print_element(v)                           for(auto d: v) cout << d << spc; cout << endl;
#define     sort_element(v)                            sort(allEmt(v));


#define     debug_one_print(x)                         cout << x << endl
#define     debug_two_print(x, y)                      cout << x << ' ' << y << endl
#define     debug_three_print(x, y, z)                 cout << x << ' ' << y << ' ' << z << endl
#define     debug_four_print(x, y, z, xx)              cout << x << ' ' << y << ' ' << z << ' ' << xx << endl
#define     long_line                                  cout << "==============\n"
#define     new_line                                   cout << newl;

const int N = 1e6+1, MOD = 1e9+7;
/*=====================================*/

class DSU{
public:
    vector<int> dsu_set;
    vector<int> dsu_rank;

    DSU(int n) {
        dsu_set.resize(n, 0);
        dsu_rank.resize(n, 0);

        for(int i=0; i<n; i++) dsu_set[i]=i;
    }

    int Find(int x) {
        if(dsu_set[x]==x) dsu_set[x]=x;
        else dsu_set[x]=Find(dsu_set[x]);
        return dsu_set[x];
    }

    void Reset(int x) {
        dsu_set[x]=x;
    }

    void Union(int x, int y) {
        int px = Find(x), py=Find(y);
        dsu_set[py] = px;
        dsu_rank[px] += 1;
    }
};

ll Pow(ll base,ll pwr, ll md){
    ll ans=1;
    while(pwr){
        if(pwr&1) ans=ans*base%md;
        base=base*base%md;
        pwr/=2;
    }
    return ans;
}

bool primeChecker(int n){
    if (n<2) return false;
    if (!(n%2) and n not_eq 2) return false;
    for(int i=3; i<=sqrt(n); i+=2) {
        if(!(n%i)) return false;
    }
    return true;
}

ll llMax(ll a, ll b) {
    return a>=b?a:b;
}
ll llMin(ll a, ll b) {
    return a<=b?a:b;
}


// int binarySearch(int b, int e, int d) {
//     if(b<e){
//         int m = (b+e)/2;
//         if(v[m]<=d) binarySearch(b, m, d);
//         else binarySearch(m+1, e, d);
//     }
//     return b+1;
// }
int binarySearch(vector <int> &v, int l, int r, int x) {
    while (l <= r) {
        int m = (l+r)/2;
        if (v[m] == x) return m;
        if (v[m] < x) l = m + 1;
        else r = m - 1;
    }
    return l;
}

bool checkV(char a) {
    if(a=='a') return true;
    else if(a=='e') return true;
    else if(a=='i') return true;
    else if(a=='o') return true;
    else if(a=='u') return true;
    else if(a=='y') return true;
    else return false;
}

bool checkPalindrome(string ch) {
    for(int i=0; i<ch.length()/2; i++) {
        if(ch[i]!=ch[ch.length()-i-1]) return false;
    }
    return true;
}

int LIS(const vector<int>& c) {
    vector <int> l;
    for(auto d: c) {
        auto it = lower_bound(l.begin(), l.end(), d);
        if(it == l.end()) {
            l.push_back(d);
        } else {
            *it = d;
        }
    }
    return l.size();
}

int substrCount(string str,string substr) {
    int count=0;
    for (int i = 0; i <str.size()-1; i++) {
        int m = 0;
        int n = i;
        for (int j = 0; j < substr.size(); j++) {
            if (str[n] == substr[j]) {
                m++;
            }
            n++;
        }
        if (m == substr.size()) {
            i+=(m-1);
            count++;
        }
    }
    return count;
}

bool substrCheck(string str,string substr) {
    int count=0;
    for (int i = 0; i <str.size()-1; i++) {
        int m = 0;
        int n = i;
        for (int j = 0; j < substr.size(); j++) {
            if (str[n] == substr[j]) {
                m++;
            }
            n++;
        }
        if (m == substr.size()) {
            return 1;
        }
    }
    return 0;
}

vector <int> seiveAlgorithm (int n) {
    vector<int>v(n+1, 1);
    v[0] = v[1] = 0;
    for(int i=2; i<=n; i++) {
        if(v[i]) {
            for(int j=2; j*i<=n; j++) {
                v[j*i] = 0;
            }
        }
    }
    return v;
}

int __lcm(int a, int b) {
    return (a / __gcd(a, b)) * b;
}

// on testing
bool checkInteger(double a) {
    if(ceil(a)==a) return false;
    return true;
}

istream& operator>>(istream& Cin, vector<ll>& v) {
    for (auto &d: v) {
        Cin >> d;
    }
    return Cin;
}
istream& operator>>(istream& Cin, vector<int>& v) {
    for (auto &d: v) {
        Cin >> d;
    }
    return Cin;
}

// istream& inputVector(istream& Cin, vector<ll>& v, int n) {
//     v.resize(n);  
//     Cin >> v; 
//     return Cin;
// }

/***************************************/
/************** Main Code **************/
/***************************************/

void solve(int tc) {
    int n, m;   cin>>n>>m;
    multiset <int> s, t;
    vector <int> v(n);
    for (int i=0; i<n; i++) {
        int a;   cin >> a;
        v[i] = a;
        s.insert(a);
    }

    int j=0;
    ll sum=0;
    ll mini = INT_MAX;
    for (int i=0; i<n; i++) {
        auto it1 = s.find(v[i]);
        s.erase(it1);
        sum += v[i];
        t.insert(v[i]);
        if(i - j + 1 == m) {
            int a = *t.rbegin();
            int b = *s.begin();
            ll temp = sum;

            if(a>b) temp -= (a-b);
            mini = llMin(temp, mini);
            auto it4 = t.find(v[j]);
            t.erase(it4);
            s.insert(v[j]);
            sum -= v[j];
            ++j;
        }
    }

    cout << mini << endl;    
    return;
}

int main(){
    Start Hunting Bugs;
    int c=1;
    int t=1;
    cin>>t;
    
    while(t--) {
        solve(c++);
    }
    Checkmate;
}

Information

Submit By
Type
Submission
Problem
P1149 Swap and Minimize
Contest
LU IUJPC : Sylhet Division 2024 Replay Contest
Language
C++17 (G++ 13.2.0)
Submit At
2024-12-10 12:16:25
Judged At
2024-12-10 12:16:25
Judged By
Score
1
Total Time
79ms
Peak Memory
576.0 KiB