| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 934855 | 2024-02-28T05:39:29 Z | PieArmy | Sirni (COCI17_sirni) | C++17 | 5000 ms | 786432 KB |
typedef long long ll;
ll pie(ll army){return (1ll<<army);}
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define endl '\n';
#define mid ((left+right)>>1)
const ll inf=2000000000000000005;
const int sonsuz=2000000005;
using namespace std;
ll fpow(ll x,ll y,ll m=0){if(y<0){cout<<"powError";return -1;}if(m)x%=m;ll res=1;while(y>0){if(y&1)res*=x;x*=x;if(m){x%=m;res%=m;}y>>=1;}return res;}
struct DSU{
int n;
vector<int>par,siz;
DSU(int N){
n=N;
par.resize(n);iota(par.begin(),par.end(),0);
siz.resize(n,1);
}
int get(int x){
if(par[x]==x)return x;
return par[x]=get(par[x]);
}
bool unite(int x,int y){
x=get(x);y=get(y);
if(x==y)return false;
if(siz[x]<siz[y])swap(x,y);
par[y]=x;
siz[x]+=siz[y];
return true;
}
};
void code(){
int n;cin>>n;
int arr[n];for(int &x:arr)cin>>x;
sort(arr,arr+n);
int mx=arr[n-1];
vector<int>v;
int las=-1;
for(int i=0;i<n;i++){
if(arr[i]!=las)v.pb(arr[i]);
las=arr[i];
}
n=v.size();
vector<int>nex(mx+2);
int pos=n-1;
for(int i=mx+1;i>=0;i--){
nex[i]=pos;
if(pos&&(i==v[pos-1])){
pos--;
nex[i]=pos;
}
}
priority_queue<vector<int>>pq;
for(int i=0;i<n;i++){
for(int j=v[i];j<=mx;j+=v[i]){
if(nex[j]==i){
pq.push({j-v[nex[j+1]],i,nex[j+1]});
continue;
}
pq.push({j-v[nex[j]],i,nex[j]});
}
}
ll ans=0;
DSU dsu(n);
while(pq.size()){
int cos=-pq.top()[0],a=pq.top()[1],b=pq.top()[2];
pq.pop();
if(dsu.unite(a,b))
ans+=cos;
}
cout<<ans;
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);
bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
int t=1;
if(!t)cin>>t;
while(t--){code();cout<<endl;}
return 0;
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 15 ms | 39772 KB | Output is correct |
| 2 | Correct | 3575 ms | 204944 KB | Output is correct |
| 3 | Correct | 22 ms | 40600 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 3 ms | 860 KB | Output is correct |
| 2 | Runtime error | 864 ms | 786432 KB | Execution killed with signal 9 |
| 3 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 16 ms | 39772 KB | Output is correct |
| 2 | Correct | 15 ms | 39516 KB | Output is correct |
| 3 | Correct | 20 ms | 40088 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 823 ms | 88876 KB | Output is correct |
| 2 | Correct | 4050 ms | 235552 KB | Output is correct |
| 3 | Correct | 1909 ms | 170784 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 85 ms | 15876 KB | Output is correct |
| 2 | Correct | 2814 ms | 170380 KB | Output is correct |
| 3 | Correct | 756 ms | 87088 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2078 ms | 169760 KB | Output is correct |
| 2 | Execution timed out | 5031 ms | 334952 KB | Time limit exceeded |
| 3 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 179 ms | 24036 KB | Output is correct |
| 2 | Execution timed out | 5039 ms | 341784 KB | Time limit exceeded |
| 3 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1519 ms | 124552 KB | Output is correct |
| 2 | Runtime error | 894 ms | 786432 KB | Execution killed with signal 9 |
| 3 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2175 ms | 144936 KB | Output is correct |
| 2 | Runtime error | 872 ms | 786432 KB | Execution killed with signal 9 |
| 3 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 105 ms | 51140 KB | Output is correct |
| 2 | Runtime error | 990 ms | 786432 KB | Execution killed with signal 9 |
| 3 | Halted | 0 ms | 0 KB | - |