【题解】走路

· · 题解

题解 走路

一句话：贪心即可。

假如有两天，比如第一天和第二天都走了路，设两天走的步数、已获得积分、接下来每步获得的积分分别为 a_1,a_2,b_1,b_2,c_1,c_2，不妨设 c_1\ge c_2。

如果我们把所有步数都放到第一天，那么我们至少会获得 b_1+a_2\times c_1 分（后面可能还有其他的激励措施）。同时，由于同一天内每一步获得的分数是递增（非严格）的，我们有

b_1+a_2\times c_1\ge b_1+a_2\times c_2\ge b_1+b_2

所以，如果分数最大，那么必定所有步数都是放在同一天。这样不是更容易猝死了吗

于是，我们对于每天计算一下如果这天走完所有步可以得到多少积分（直接读入时累加即可），然后取个最大的即可。

\texttt{code}: 
#include<cstdio>
#include<iostream>
#include<fstream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
#define Set(a) memset(a,0,sizeof(a))
#define F(i,a,b) for(register int i=a,i##end=b;i<=i##end;++i)
#define UF(i,a,b) for(register int i=a,i##end=b;i>=i##end;--i)
#define openf(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define re register
#define ri re int
#define il inline
typedef long long ll;
typedef unsigned long long ull;
template<typename T> inline T rd(T& x)
{
    T f=1;x=0;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(T)(c-'0');
    x*=f;
    return x;
}
ll rd(){ll x;rd(x);return x;}
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
const int inf=1<<30;

ll a[100005];
ll n,m,k,mx=0;
int main()
{
    rd(n);rd(m);rd(k);
    F(i,1,k) {ll p=rd();ll q=rd();a[p]+=n-q;}
    F(i,1,m) if(a[i]>=a[mx]) mx=i;
    cout<<a[mx]<<endl;
    return 0;
}