Submission #1211760

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211760		ASGA_RedSea	Detecting Molecules (IOI16_molecules)	C++17	9 / 100	6 ms	424 KiB

molecules

/**

                                    * بسم الله الرحمن الرحيم *

                ﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿

*/

/// author : "ASGA"

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;
using ll = long long;


vector<int>find_subset(int l,int r,vector<int>a){
    vector<ll>w(a.begin(),a.end());
    if(accumulate(w.begin(),w.end(),0LL)<l)return {};


    int n=a.size();
    vector<vector<int>>f(r+1);
    for(int i=0;i<n;i++){
        if(a[i]<=r){
            f[a[i]].push_back(i);
        }
    }
    sort(a.rbegin(),a.rend());

    multiset<ll>ss(a.begin(),a.end()),sss;

    vector<int>d(r+1,-1);
    d[0]=0;
    int mx=0;
    for(int&i:a){
        for(int j=r;j>=i;j--){
            if(d[j-i]!=-1){
                d[j]=j-i;
                mx=max(mx,j);
            }
        }

        for(int j=1;j<=r;j++){
            if(d[j]!=-1){
                sss=ss;
                int jj=j;
                while(jj>0){
                    assert(sss.find(jj-d[jj])!=sss.end());
                    sss.erase(sss.find(jj-d[jj]));
                    jj=d[jj];
                }
            }
        }
    }

    if(mx<l)return {};

    vector<int>ret;
    ll tot=0;
    int mmx=mx;
    while(mx>0){
        ret.push_back(f[mx-d[mx]].back());
        f[mx-d[mx]].pop_back();
        mx=d[mx];
    }
    for(int&i:ret)tot+=w[i];
    //assert(tot==mmx);
    return ret;
}

Compilation message (stderr)

molecules.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
molecules_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• Subtask 1: 9 / 9
• Subtask 2: 0 / 10
• Subtask 3: 0 / 12
• Subtask 4: 0 / 15
• Subtask 5: 0 / 23
• Subtask 6: 0 / 31