結果

問題 No.1430 Coup de Coupon
ユーザー tails
提出日時 2022-10-21 12:21:05
言語 C90
(gcc 12.3.0)
結果
AC  
実行時間 18 ms / 2,000 ms
コード長 1,580 bytes
コンパイル時間 499 ms
コンパイル使用メモリ 28,912 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-30 22:56:04
合計ジャッジ時間 1,875 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 27
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function ‘main’:
main.c:90:17: warning: implicit declaration of function ‘write’ [-Wimplicit-function-declaration]
   90 |                 write(1,wp,wbuf+sizeof wbuf-wp);
      |                 ^~~~~
main.c:92:9: warning: implicit declaration of function ‘_exit’ [-Wimplicit-function-declaration]
   92 |         _exit(0);
      |         ^~~~~
main.c:92:9: warning: incompatible implicit declaration of built-in function ‘_exit’ [-Wbuiltin-declaration-mismatch]

ソースコード

diff #
プレゼンテーションモードにする

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#define rd() ({int _v=0,_c;while(_c=*rp++-48,_c>=0)_v=_v*10+_c;_v;})
#define wt(v) {unsigned _z=v;do*--wp=_z%10+48;while(_z/=10);}
#define rep(v,e) for(long v=0;v<e;++v)
#define rrep3(v,s,e) for(long v=e;--v>=s;)
#define min(a,b) (a<=b?a:b)
#define max(a,b) (a>=b?a:b)
#define chmin(v,a) (v=v<=a?v:a)
#define chmax(v,a) (v=v>=a?v:a)
void radix_sort_aux(unsigned*a,unsigned*b,int n){
    int c[256];
    for(int i=0;i<256;++i){
        c[i]=0;
    }
    for(int i=0;i<n;++i){
        ++c[a[i]&255];
    }
    int t=0;
    for(int i=256;i--;){
        int u=c[i];
        c[i]=t;
        t+=u;
    }
    for(int i=0;i<n;++i){
        b[c[a[i]&255]++]=a[i]>>8|a[i]<<24;
    }
}
void radix_sort(unsigned*a,int n){
    static unsigned b[5000];
    radix_sort_aux(a,b,n);
    radix_sort_aux(b,a,n);
    radix_sort_aux(a,b,n);
    radix_sort_aux(b,a,n);
}
int p[5000];
int x1[5000];
int x2[5000];
int d[5001];
int main(){
    char*mmap();
    char*rp=mmap(0l,1l<<25,1,2,0,0ll);
    int n=rd();
    int c=rd();
    int s=0;
    rep(i,n){
        int p0=rd();
        p[i]=p0;
        s+=p0;
    }
    radix_sort(p,n);
    chmin(n,c);
    int c1=0,c2=0;
    rep(i,c){
        int t=*rp;
        rp+=2;
        int x=rd();
        if(t&1){
            x1[c1++]=x;
        }else{
            x2[c2++]=x;
        }
    }
    radix_sort(x1,c1);
    radix_sort(x2,c2);
    int di=0;
    int dn=1;
    rep(i,n){
        int pi=p[i];
        di+=i-di<0;
        dn+=dn<=c2;
        rrep3(j,di,dn){
            int y1=i-j<c1?d[j]+min(pi,x1[i-j]):0;
            int y2=j-1>=0?d[j-1]+pi/100*x2[j-1]:0;
            d[j]=max(y1,y2);
        }
    }
    {
        int z=0;
        rrep3(j,di,dn){
            chmax(z,d[j]);
        }
        char wbuf[64],*wp=wbuf+sizeof wbuf;
        wt(s-z);
        write(1,wp,wbuf+sizeof wbuf-wp);
    }
    _exit(0);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0