Submission #825193

#	Time	Username	Problem	Language	Result	Execution time	Memory
825193		Amylopectin	Let's Win the Election (JOI22_ho_t3)	C++14	100 / 100	101 ms	4280 KiB

Main

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int mxn = 2010,mxi = 1e9 + 10;
struct we
{
    double aa,bb;
    int idx;
};
bool cmp1(const struct we &l,const struct we &r)
{
    return l.aa < r.aa;
}
bool cmp2(const struct we &l,const struct we &r)
{
    if(l.bb == -1)
    {
        return false;
    }
    if(r.bb == -1)
    {
        return true;
    }
    if(l.bb == r.bb)
    {
        return l.aa > r.aa;
    }
    return l.bb < r.bb;
}
struct we soa[mxn] = {},sob[mxn] = {};
int u[mxn] = {};
double dp[mxn][mxn] = {};
int main()
{
    int i,j,k,o,n,m,cn,cm,fn,fm,cru,fru,cou;
    double cva,cmi = mxi,f,p,csu;
    scanf("%d %d",&n,&m);
    for(i=0; i<n; i++)
    {
        scanf("%lf %lf",&soa[i].aa,&soa[i].bb);
    }
    sort(soa,soa+n,cmp1);
    for(i=0; i<n; i++)
    {
        soa[i].idx = i;
        sob[i] = {soa[i].aa,soa[i].bb,i};
    }
    sort(sob,sob+n,cmp2);
    cru = n;
    for(i=0; i<n; i++)
    {
        if(sob[i].bb == -1)
        {
            cru = i;
            break;
        }
    }

    for(i=0; i<=min(cru,m); i++)
    {
        f = i+1;
        dp[0][0] = sob[0].aa / f;
        dp[0][1] = sob[0].bb;
        for(j=2; j<=i; j++)
        {
            dp[0][j] = mxi;
        }
        for(j=0; j<n; j++)
        {
            u[j] = 0;
        }
        fru = m;
        cou = m;
        csu = 0;
        for(j=0; j<m; j++)
        {
            csu += soa[j].aa / f;
        }
        if(i == 0)
        {
            cmi = min(cmi,csu);
        }
        for(j=0; j<min(cru,m); j++)
        {
            if(j > 0)
            {
                for(k=0; k<=i; k++)
                {
                    dp[j][k] = dp[j-1][k] + sob[j].aa / f;
                    if(k > 0)
                    {
                        p = k;
                        dp[j][k] = min(dp[j][k],dp[j-1][k-1] + sob[j].bb / p);
                    }
                }
            }
            if(sob[j].idx >= fru)
            {
                while(u[fru-1] == 1)
                {
                    fru --;
                }
                csu -= soa[fru-1].aa / f;
                fru --;
            }
            else 
            {
                csu -= sob[j].aa / f;
            }
            u[sob[j].idx] = 1;
            cmi = min(cmi,dp[j][i] + csu);
        } 
    }
    printf("%lf\n",cmi);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:36:15: warning: unused variable 'o' [-Wunused-variable]
   36 |     int i,j,k,o,n,m,cn,cm,fn,fm,cru,fru,cou;
      |               ^
Main.cpp:36:21: warning: unused variable 'cn' [-Wunused-variable]
   36 |     int i,j,k,o,n,m,cn,cm,fn,fm,cru,fru,cou;
      |                     ^~
Main.cpp:36:24: warning: unused variable 'cm' [-Wunused-variable]
   36 |     int i,j,k,o,n,m,cn,cm,fn,fm,cru,fru,cou;
      |                        ^~
Main.cpp:36:27: warning: unused variable 'fn' [-Wunused-variable]
   36 |     int i,j,k,o,n,m,cn,cm,fn,fm,cru,fru,cou;
      |                           ^~
Main.cpp:36:30: warning: unused variable 'fm' [-Wunused-variable]
   36 |     int i,j,k,o,n,m,cn,cm,fn,fm,cru,fru,cou;
      |                              ^~
Main.cpp:36:41: warning: variable 'cou' set but not used [-Wunused-but-set-variable]
   36 |     int i,j,k,o,n,m,cn,cm,fn,fm,cru,fru,cou;
      |                                         ^~~
Main.cpp:37:12: warning: unused variable 'cva' [-Wunused-variable]
   37 |     double cva,cmi = mxi,f,p,csu;
      |            ^~~
Main.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
Main.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         scanf("%lf %lf",&soa[i].aa,&soa[i].bb);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 33 / 33
• Subtask 6: 11 / 11
• Subtask 7: 23 / 23