akhauriyash/Code-Regression huggingface dataset:
<?php /*atcoder.php*/

$at = new Atcoder();
$at->main();
unset($at);

class Atcoder{
	private function arrayIn(){
		$buf = explode(" ", fgets(STDIN));
		return $this->killNewLine($buf);
	}
	private function killNewLine($buf = null){
		$buf = str_replace("\r\n", "", $buf);
		$buf = str_replace("\n", "", $buf);
		$buf = str_replace("\r", "", $buf);
		return $buf;
	}

	public function main(){
		$s = $this->arrayIn();
		
		$n = $s[0];
		$m = $s[1];

		$ans = 0;
		
		$a = array();
		for($i = 0; $i < $n; $i++){
			$s = $this->arrayIn();
			$a[$s[0]] += $s[1];
		}

		ksort($a);

		$buf = 0;
		$b = 0;
		foreach($a as $k => $v){
			if($m == $buf){break; };
			if(0 < ($m - $buf - $v)){
				$ans += $v * $k;
				$buf += $v;
			}else{
				$b = $m - $buf;
				$ans += $b * $k;
				$buf += $b;
			}
		}
		unset($k);
		unset($v);
		
		echo $ans . "\n";

	}
}
?>


Measured memory_bytes: 13048
#include <bits/stdc++.h>
using namespace std;

#define DEBUG(x) cerr << #x << ": " << x << endl;
#define ll long long

int main() {
    int a, b;
    cin >> a >> b;

    if (a == 1) {
        if (b == 1) {
            cout << "Draw" << endl;
            return 0;
        } else {
            cout << "Alice" << endl;
            return 0;
        }
    } else if (b == 1) {
        if (a == 1) {
            cout << "Draw" << endl;
            return 0;
        } else {
            cout << "Bob" << endl;
            return 0;
        }
    }

    if (a > b) {
        cout << "Alice" << endl;
    } else if (a < b) {
        cout << "Bob" << endl;
    } else { 
        cout << "Draw" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;cin>>N;
  vector<int> a(N);
  for(int i=0; i<N; i++)cin>>a[i];
  sort(a.begin(),a.end());
  cout<<abs(a[0]-a[a.size()-1])<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>

int get_max(int num, int array[num]);

int get_min(int num, int array[num]);

int main(void){
    int numx, numy, capx, capy;
    int *areax, *areay;
    int i;

    scanf("%d %d %d %d", &numx, &numy, &capx, &capy);

    areax = (int *)malloc(numx * sizeof(int));
    areay = (int *)malloc(numy * sizeof(int));

    for(i = 0; i < numx; i++){
        scanf("%d", &areax[i]);
    }

    for(i = 0; i < numy; i++){
        scanf("%d", &areay[i]);
    }

    //printf("areax_max = %d, areay_min = %d\ncapy = %d, capx = %d\n", get_max(numx, areax), get_min(numy, areay), capy, capx);

    if(get_max(numx, areax) < get_min(numy, areay)
        && get_max(numx, areax) < capy
        && get_min(numy, areay) > capx){
        printf("No War\n");
    }else{
        printf("War\n");
    }
    return 0;
}

int get_max(int num, int array[num]){
    int max = -100, loopmax;
    for(loopmax = 0; loopmax < num; loopmax++){
        if(max < array[loopmax])
            max = array[loopmax];
    }
    return max;
}

int get_min(int num, int array[num]){
    int min = 100, loopmin;
    for(loopmin = 0; loopmin < num; loopmin++){
        if(min > array[loopmin])
            min = array[loopmin];
    }
    return min;
}

Measured memory_bytes: 128
var restaurants = [(Int, String, Int)]()
for i in 1...Int(readLine()!)! {
  let input = readLine()!.characters.split(" ").map{String($0)}
  restaurants += [(i, input[0], Int(input[1])!)]
}
restaurants.sortInPlace{
  if $0.1==$1.1 {
    return $0.2>$1.2
  }
  return $0.1<$1.1
}
for restaurant in restaurants {
  print(restaurant.0)
}

Measured memory_bytes: 6128
#include <iostream>//cout
#include <stdio.h>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <functional>
#include <list>
#include <utility>//swap
using namespace std;
static const int MAX = 200000;
#define rep(i,n) for(int i=0;i<n;i++)
#define GET_ARRAY_SIZE(a) (sizeof(a)/sizeof(a[0]))

int main() {
  int x;
  cin >> x;
  if(x < 1200){
    cout << "ABC" << endl;
  } else {
    cout << "ARC" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <math.h>
#include <string>
#include <map>
#include <cstdlib>
#include <sstream>
#include <bitset>
#include <iomanip>
#include <time.h>
using namespace std;

typedef long long ll;
typedef pair<double,int> P;

ll dp[3000][3000][4];
ll value[3000][3000];

int main()
{
    ll H,W,K;
    cin >> H >> W >> K;
    for(int i=0; i<K; i++){
        int h,w,v;
        cin >> h>> w >> v;
        h--;w--;
        value[h][w]=v;
    }
    // for(int i=0; i<H; i++){
    //     for(int j=0; j<W; j++){
    //         cout << value[i][j];
    //     }
    // }

    if(value[0][0]!=0) dp[0][0][1]=value[0][0];
    for(int h=0; h<H; h++){
        for(int w=0; w<W; w++){
            dp[h][w][1]=value[h][w];
            if(1<=h){
                for(int i=0; i<4; i++){
                    dp[h][w][0]=max(dp[h][w][0],dp[h-1][w][i]);
                }
                dp[h][w][1]=max(dp[h][w][1],dp[h][w][0]+value[h][w]);
                for(int i=0; i<4; i++){
                    dp[h][w][1]=max(dp[h][w][1],dp[h-1][w][i]+value[h][w]);
                }
            }
            if(1<=w){
                dp[h][w][0]=max(dp[h][w][0],dp[h][w-1][0]);
                dp[h][w][1]=max(dp[h][w][1],dp[h][w][0]+value[h][w]);
                for(int i=1; i<4; i++){
                    dp[h][w][i]=max(dp[h][w][i],dp[h][w-1][i]);
                    dp[h][w][i]=max(dp[h][w][i],dp[h][w-1][i-1]+value[h][w]);
                }
            }
        }
    }
    
    ll ans=0;
    for(int i=0; i<4; i++){
        ans=max(ans,dp[H-1][W-1][i]);
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 354920
from collections import defaultdict

n, a = map(int, input().split())
x = list(map(int, input().split()))
y = [xi - a for xi in x]

# 解説AC
dp = [defaultdict(int) for i in range(n + 1)]
dp[0][0] = 1

for i in range(n):
    for j in dp[i]:
        dp[i + 1][j + y[i]] += dp[i][j]
        dp[i + 1][j] += dp[i][j]

print(dp[n][0] - 1)


Measured memory_bytes: 74388
N, A, B, C, D = map(int, input().split())
S = input()

AtoC = True
BtoD = True
replace = False

for n in list(range(A-1,C)):
    if S[n] =='#' and S[n+1] =='#':
        AtoC = False
        
for n in list(range(B-1,D)):
    if S[n] =='#' and S[n+1] == '#':
        BtoD = False
        
if C<D:
    if AtoC == True and BtoD == True:
        print('Yes')
    else:
        print('No')
else:
    for n in list(range(B-2,D-1)):
        if S[n] =='.' and S[n+1] == '.' and S[n+2] == '.':
            replace = True
    if AtoC == True and BtoD == True and replace == True:
        print('Yes')
    else:
        print('No')

Measured memory_bytes: 11060
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main(void)
{
  ll N;
  cin>>N;
  if(N%2==1){
    cout<<0<<endl;
    return 0;
  }

  ll num =10;
  ll sum =0;
  while(true){
    sum += N/num;
    //cout<<N/num<<" "<<N<<" "<<num<<endl;
    if(N/5 >= num){
    num*=5;
    }
    else{
      break;
    }
  }

  cout<<sum<<endl;

  return 0;
}

Measured memory_bytes: 256
def init
  x = 1
  while x <= $n
    x <<= 1
  end
  $n = x
  $arr = (2 * $n - 1).times.map{ |i| [i - $n + 1, 0] }
end

def update(i, m)
  i += $n - 1
  $arr[i][1] += m
  while i > 0
    i = (i - 1) / 2
    $arr[i] = $arr[i*2+1][1] >= $arr[i*2+2][1] ? $arr[i*2+1] : $arr[i*2+2]
  end
end

$n, q = gets.split.map(&:to_i)
init
q.times do
  i, m = gets.split.map(&:to_i)
  update(i, m)
  puts $arr[0].join(' ')
end

Measured memory_bytes: 179936
//#pragma GCC optimize(2)
#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<climits>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
int read(){
    int f=1,x=0;char c=getchar();
    while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();}
    while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f==1?x:-x;
}
#define MAXN 5000
#define MAXM 5000
#define INF 0x3f3f3f3f
struct edge{ int v,w;};
vector<edge> G[MAXN+5],H[MAXN+5];
inline void Addedge(int u,int v,int w){
	//printf("\n*%d %d %d*\n\n",u,v,w);
	G[u].push_back((edge){v,w});
	H[v].push_back((edge){u,w});
	return ;
}
queue<int> Q;
LL dis[MAXN+5];
bool vis[MAXN+5];
int n,m,P,cnt[MAXN+5];
bool vis1[MAXN+5],vis2[MAXN+5];
LL SPFA(int S,int T){
	memset(vis,0,sizeof(vis));
	memset(dis,-0x3f,sizeof(dis));
	dis[S]=0,vis[S]=1,cnt[S]++,Q.push(S);
	while(!Q.empty()){
		int u=Q.front();Q.pop();
		vis[u]=0;
		for(int i=0;i<int(G[u].size());i++){
			int v=G[u][i].v,w=G[u][i].w;
			if(vis1[v]&&vis2[v]&&dis[v]<dis[u]+w){
				dis[v]=dis[u]+w;
				if(!vis[v]){
					cnt[v]++;
					if(cnt[v]>n)
						puts("-1"),exit(0);
					vis[v]=1,Q.push(v);
				}
			}
		}
	}
	return dis[T];
}
void DFS1(int u,int fa){
	vis1[u]=1;
	for(int i=0;i<int(G[u].size());i++){
		int v=G[u][i].v;
		if(vis1[v]) continue;
		DFS1(v,u);
	}
	return ;
}
void DFS2(int u,int fa){
	vis2[u]=1;
	for(int i=0;i<int(H[u].size());i++){
		int v=H[u][i].v;
		if(vis2[v]) continue;
		DFS2(v,u);
	}
	return ;
}
int main(){
	n=read(),m=read(),P=read();
	for(int i=1;i<=m;i++){
		int u=read(),v=read(),w=read()-P;
		Addedge(u,v,w);
	}
	DFS1(1,0),DFS2(n,0);
	printf("%lld\n",max(0ll,SPFA(1,n)));
    return 0;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
   
using namespace std;
#define ll long long
#define ld long double
#define pll pair<long long,long long>
#define vll vector<long long>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define deb(x) cout << #x << "=" << x << endl
#define F(i,a,b) for(ll i=a;i<=b;i++)
#define RF(i,a,b) for(ll i=a;i>=b;i--)
#define in(a,n) F(i,0,n-1)cin>>a[i]
#define vi vector<int>
#define out(a,n) F(i,0,n-1)cout<<a[i]<<" ";cout<<endl
#define mod 1000000007
#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
#define int long long
const int N=(int)3e3+5,INF=(int)1e18+7;

string s,t;
int n,m;

int dp[N][N];
string answer="";
int solve(int i1,int i2)
{
    if(i1==n or i2==m)return 0;
    
    int &ans=dp[i1][i2];
    if(ans!=-1)return ans;
    ans=0;
    int op1=0,op2=0,op3=0;
    if(s[i1]==t[i2]){
        
    op1=1+solve(i1+1,i2+1);
    
    }
    op2=solve(i1+1,i2);
    op3=solve(i1,i2+1);
    return ans=max({op1,op2,op3});
}

void path(int i1,int i2)
{
   
    if(i1==n or i2==m)return;
    
    int cur=dp[i1][i2];
    
    if(s[i1]==t[i2] and (cur==(1+solve(i1+1,i2+1))))
    {
        
        answer+=s[i1];
        path(i1+1,i2+1);
        return;
    }
    
    if(cur==solve(i1,i2+1))
    {
        path(i1,i2+1);
        return ;
    }
    if(cur==solve(i1+1,i2))
    {
        path(i1+1,i2);
        return;
    }
}

void solve()
{
   cin>>s>>t;
    n=s.size(),m=t.size();
   // cout<<n<<" "<<m<<'\n';
   memset(dp,-1,sizeof dp);
   
   int ans=solve(0,0);
 
   path(0,0);
   cout<<answer;
   
}

int32_t main()
{
	ios::sync_with_stdio(false);
    cin.tie(NULL);
    
	int t=1;
	//cin>>t;
	while(t--)solve();
	    
   
}


Measured memory_bytes: 74612
#include <bits/stdc++.h>

using namespace std;

const int INF = 1000000001;
int r[100002];

static inline int magic(int l, int x, int r) {
  return max(min(r, x), l);
}

static inline void slide(int h, int dist, int &mina, int &minb, int &maxa, int &maxb) {
  minb = magic(0, minb + dist, h);
  maxb = magic(0, maxb + dist, h);
  if(maxb - minb < maxa - mina) {
    int delta = (maxa - mina) - (maxb - minb);
    if(dist < 0)
      mina += delta;
    else
      maxa -= delta;
  }
}

int main() {
  int h, n, q, t, a, mina, maxa, minb, maxb, dist, j;
#ifdef DEBUG
  freopen("codeforces.in", "r", stdin);
  freopen("codeforces.out", "w", stdout);
#endif
  scanf("%d%d", &h, &n);
  for(int i = 1; i <= n; ++i)
    scanf("%d", &r[i]);
  r[n + 1] = INF;
  n = n + 2;
  j = 1;
  mina = minb = 0;
  maxa = maxb = h;
  scanf("%d", &q);
  for(int i = 0; i < q; ++i) {
    scanf("%d%d", &t, &a);
    while(r[j] < t) {
      dist = r[j] - r[j - 1];
      if(j % 2 == 1)
        dist = -dist;
      slide(h, dist, mina, minb, maxa, maxb);
      ++j;
    }
    dist = t - r[j - 1];
    if(j % 2 == 1)
      dist = -dist;
    slide(h, dist, mina, minb, maxa, maxb);
    r[j - 1] = t;
    a = magic(mina, a, maxa);
    printf("%d\n", maxb - (maxa - a));
  }
  return 0;
}


Measured memory_bytes: 1536
#include<iostream>
#include <string>
using namespace std;

int main() {
  string s;
  cin >> s;
  int res = 1e9;
  for (int i = 0; i < (int)s.size()-2; i++) {
    int a = (s[i]-'0')*100 + (s[i+1]-'0')*10 + (s[i+2]-'0');
    res = min(res, abs(a-753));
  }
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 256
#include<algorithm>
#include<climits>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<list>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<utility>
#include<vector>
 
#define lint long long
#define REP(i, x, n) for(int i = x ; i < n ; i++)
#define rep(i, n) REP(i, 0, n)
#define repr(i, n) for(int i = n - 1 ; i >= 0 ; i--)
#define SORT(c) sort((c).begin(), (c).end())
#define SORT_INV(c) sort((c).begin(), (c).end(), greater<int>())
#define IINF INT_MAX
#define LLINF LLONG_MAX

using namespace std;

int main(){
    int a, b, c;
    cin >> a >> b >> c;
    bool flag = false;
    for(int i = 1 ; i <= b ; i++){
        if((a*i)%b==c){
            flag = true;
            break;
        }
    }
    if(flag){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main
{
	public static void main(String[] args) {
	    Scanner read = new Scanner(System.in);
	    int n = read.nextInt();
	    int x[] = new int[n];
	    for(int i=0; i<n; i++){
	        x[i] = read.nextInt();
	    }
	    int c = 0;
	    for(int i=0; i<n; i++){
	        if (i == 0 || i == n-1){
	            continue;
	        }else if((x[i] < x[i-1] && x[i] > x[i+1]) || (x[i] < x[i+1] && x[i] > x[i-1])){
	            c++;
	        }
	    }
		System.out.println(c);
	}
}

Measured memory_bytes: 22228
#include<bits/stdc++.h>
using namespace std;

int ara[105];

int main()
{
  int n,m;
  cin>>n>>m;
  
  int sum=0;
  for(int i=0;i<n;i++) 
  {
    cin>>ara[i];
    sum+=ara[i];
  }
  
  int limit=sum/(4*m);
  if(sum%(4*m)) limit++;
  
  int tot=0;
  
  for(int i=0;i<n;i++)
  {
    if(ara[i]>=limit) tot++;
  }
  
  if(tot>=m) cout<<"Yes";
  else cout<<"No";
  
}
  
  

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
#define mod 1000000007LL
#define nax 500009LL
#define FOR(i,n,m) for(int i = (n); i < (m); i++)
#define REP(i,n) FOR(i,0,n)
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
#define all(v) v.begin(),v.end()
#define sz(v) int(v.size())
 
 
typedef long long ll;
typedef vector<int> vi; 
typedef pair<int,int> ii;
 

int main(){
	fastio;
    
	int n, m; cin>>n>>m;
	bool p[nax];
	memset(p, 0, sizeof p);
	int x;
	REP(i,m) cin>>x, p[x]=1;

	int dp[nax];

	dp[0]=1;
	if(p[1]){
		dp[1]=0;
	}
	else{
		dp[1]=1;
	}
	FOR(i,2,n+1){
		if(p[i]){
			dp[i]=0;
		}
		else{
			if(!p[i-1]){
                dp[i]+=dp[i-1];
                dp[i]=dp[i]%mod;
            }
            if(!p[i-2]){
                dp[i]+=dp[i-2];
                dp[i]=dp[i]%mod;
            }
		}
	}

    cout<<dp[n];


	return 0;
}

Measured memory_bytes: 4520
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);

		while(stdIn.hasNext()){
			int sum = 0;
			for(int i=0;i<5;i++){
				int tmp = stdIn.nextInt();
				if(tmp<40) tmp = 40;
				sum += tmp;
			}
			System.out.println(sum/5);
		}
	}
}

Measured memory_bytes: 17360
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define dump(x) cout << #x << " = " << (x) << endl;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define int long long
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int x, y, z, k;
  cin >> x >> y >> z >> k;
  vector<int> A(x);
  REP(i, x) cin >> A[i];
  vector<int> B(y);
  REP(i, y) cin >> B[i];
  vector<int> C(z);
  REP(i, z) cin >> C[i];
  vector<int> AB;
  for(int i = 0; i < x; i++) {
    for(int j = 0; j < y; j++) {
      AB.push_back(A[i] + B[j]);
    }
  }
  sort(rall(AB));
  sort(rall(C));
  vector<int> ans;
  for(int i = 0; i < k && i < AB.size(); i++) {
    for(int j = 0; j < k && j < z; j++) {
      ans.push_back(AB[i] + C[j]);
    }
  }
  sort(rall(ans));
  for(int i = 0; (i < k); i++) {
    cout << ans[i] << endl;
  }

  return 0;
}

Measured memory_bytes: 42984
n = int(input())
W = [input() for i in range(n)]
flg = 1

Word = [W[0]]
for i in range(1,n):
    s = W[i-1]
    t = W[i]
    
    if(s[-1] != t[0] or t in Word): 
        flg = 0
        break
    Word.append(t)
    
if (flg): print("Yes")
else: print("No")



Measured memory_bytes: 9132
#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    while (N--) {
        int k, p;
        cin >> k >> p;

        int mod = k % p;
        if (mod) cout << mod << endl;
        else cout << p << endl;
    }

    return 0;
}

Measured memory_bytes: 3108
#include <bits/stdc++.h>
using namespace std;

#define d(x) cerr << #x ":" << x << endl;
#define dd(x, y) cerr << "(" #x "," #y "):(" << x << "," << y << ")" << endl
#define rep(i, n) for (int i = (int)(0); i < (int)(n); i++)
#define repp(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define all(v) v.begin(), v.end()
#define dump(v)                  \
    cerr << #v ":[ ";            \
    for (auto macro_vi : v) {    \
        cerr << macro_vi << " "; \
    }                            \
    cerr << "]" << endl;
#define ddump(v)                           \
    cerr << #v ":" << endl;                \
    for (auto macro_row : v) {             \
        cerr << "[";                       \
        for (auto macro__vi : macro_row) { \
            cerr << macro__vi << " ";      \
        }                                  \
        cerr << "]" << endl;               \
    }
using lint       = long long;
const int INF    = 1e9;
const lint LINF  = 1e18;
const lint MOD   = 1e9 + 7;
const double EPS = 1e-10;

int main() {
    lint N, M;
    cin >> N >> M;
    lint sum = 0;
    rep(i, M) {
        lint tmp;
        cin >> tmp;
        sum += tmp;
    }
    if (N < sum) {
        cout << -1 << endl;
    } else {
        cout << N - sum << endl;
    }
    return 0;
}

Measured memory_bytes: 3588
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;

int main() {
  int n, m;
  cin >> n >> m;
  priority_queue<pair<int, int>> cards;
  rep(i, n) {
    int a;
    cin >> a;
    cards.push(make_pair(a, 1));
  }
  rep(i, m) {
    int b, c;
    cin >> b >> c;
    cards.push(make_pair(c, b));
  }

  ll ans = 0;
  rep(i, n) {
    pair<int,int> p = cards.top();
    cards.pop();
    ans += p.first;
    if (p.second > 1) {
      p.second--;
      cards.push(p);
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 2420
n = int(input())

p = [int(i) for i in input().split()]

p_sort = sorted(p)

count = 0

for i in range(n):
    if p[i] != p_sort[i]:
        count += 1

if count == 2 or count == 0:
    print('YES')

else:
    print('NO')

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
bool linkSearch(int *A,int n,int key){
	A[n]=key;
	int i=0;
	while(A[i]!=key){
		i++;
	}
	return n!=i;
}
int main(){
	int n;
	cin>>n;
	
	int a[n+1];
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	
	int q;
	cin>>q;
	
	int key,sum=0;
	for(int i=0;i<q;i++){
		cin>>key;
		if(linkSearch(a,n,key)){
			sum++;
		}
	}
	cout<<sum<<endl;
	return 0;
} 


Measured memory_bytes: 3120
#include <cassert>
#include <iostream>
#include <string>
#include <vector>

int main()
{
  int slen, q;
  std::cin >> slen >> q;
  std::string input;
  std::cin >> input;
  std::vector<int> total_ac;
  char prev_ch = '\0';
  int ac_cnt = 0;
  for (char ch : input) {
    if (prev_ch == 'A' && ch == 'C') {
      ac_cnt++;
    }
    total_ac.push_back(ac_cnt);
    prev_ch = ch;
  }
  assert((int)total_ac.size() == slen);
  for (int i = 0; i < q; i++) {
    int first, last;
    std::cin >> first >> last;
    std::cout << total_ac.at(last-1) - total_ac.at(first-1) << '\n';
  }
  return 0;
}


Measured memory_bytes: 1528
#import<cstdio>
#define k 1024
#define r(a) for(int i=0;i<a;i++)
#define s(a) scanf("%d",a);
#define m(a,b) a=a<b?a:b
int w,n,m,c[k],d[k],p[k];main(){s(&n)s(&m)r(n)s(d+i)r(m)s(c+i)r(n)p[i]=1e9;r(m*n)w=i%n,m(p[w],p[w+1]+c[i/n]*d[n-w-1]);printf("%d\n",p[0]);}

Measured memory_bytes: 1040
#include <bits/stdc++.h>

using namespace std;

using i64 = long;

const i64 MOD = 1e9 + 7;
const i64 INF = 1e18 + 7;


signed main(){
    string s;
    i64 k;
    cin >> s >> k;
    i64 n = s.size();
    if(n == 1){
        cout << k / 2 << endl;
        return 0;
    }
    vector<i64> a(n);
    for(i64 i = 0; i < n; ++i)
        a[i] = s[i] - 'a';

    vector<vector<i64>> ans(26);
    for(i64 c = 0; c < 26; ++c){
        vector<i64> dp(26, INF);
        dp[c] = 0;
        for(i64 i = 0; i < n; ++i){
            vector<i64> nex(26, INF);
            for(i64 j = 0; j < 26; ++j){
                for(i64 k = 0; k < 26; ++k){
                    nex[k] = min(nex[k], dp[j] + 1);
                    if(a[i] == k && k != j)
                        nex[k] = min(nex[k], dp[j]);
                }
            }
            dp = move(nex);
        }
        ans[c] = move(dp);
    }

    auto merge = [&](auto x, auto y){
        vector<vector<i64>> z(26, vector<i64>(26, INF));
        for(int i = 0; i < 26; ++i){
            for(int j = 0; j < 26; ++j){
                for(int k = 0; k < 26; ++k){
                    z[i][j] = min(z[i][j], x[i][k] + y[k][j]);
                }
            }
        }
        return z;
    };
    auto mat = k & 1 ? ans : vector<vector<i64>>(26, vector<i64>(26, 0));
    auto u = ans;
    while(u = merge(u, u), k >>= 1)
        if(k & 1)
            mat = merge(mat, u);

    i64 ret = INF;
    for(i64 i = 0; i < 26; ++i){
        for(i64 j = 0; j < 26; ++j){
            ret = min(ret, mat[i][j]);
        }
    }
    cout << ret << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define Rint register int
using namespace std;
const int N = 100003;
template<typename T>
inline void read(T &x){
    int ch = getchar(); x = 0;
    for(;ch < '0' || ch > '9';ch = getchar());
    for(;ch >= '0' && ch <= '9';ch = getchar()) x = x * 10 + ch - '0';
}
int n, a[N];
int main(){
    read(n);
    for(Rint i = 1;i <= n;++ i) read(a[i]);
    sort(a + 1, a + n + 1, greater<int>());
    for(Rint i = 1;i <= n;++ i)
        if(a[i + 1] < i + 1){
            int j = 0;
            for(;a[j + i + 1] == i;++ j);
            if((a[i] - i & 1) || (j & 1)) puts("First");
            else puts("Second");
            return 0;
        }
}

Measured memory_bytes: 640
n=int(input())
s=input()
t=input()
n=len(s)
mod=10**9+7
ans=1
i=0
while i<n:
  if i==0:
    if s[i]==t[i]: 
      ans*=3
      i+=1
    else:
      ans*=6
      i+=2
    continue
  if s[i-1]!=t[i-1] and s[i]==t[i]:
    ans*=1
    i+=1
  elif s[i-1]==t[i-1] and s[i]!=t[i]:
    ans*=2
    i+=2
  elif s[i-1]!=t[i-1] and s[i]!=t[i]:
    ans*=3
    i+=2
  elif s[i-1]==t[i-1] and s[i]==t[i]:
    ans*=2
    i+=1
  ans%=mod
print(ans)


Measured memory_bytes: 3064
#include <bits/stdc++.h>

#define INF INT_MAX
#define UINF UINT_MAX
#define MOD 1000000007
#define REP(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()

typedef long long ll;
typedef std::pair<int,int> pii;

using namespace std;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    string s;
    cin >> s;

    for(int i = 0;i <= s.size()/2;i++){
        // cout << s[i]  << " " <<  s[(s.size()-2)/2 - i] << endl;
        if(s[i] != s[s.size() - 1 - i]){
            cout << "No" << endl;
            return 0;
        }
    }

    for(int i = 0;i <= (s.size()-1)/4;i++){
        // cout << s[i]  << " " <<  s[(s.size()-2)/2 - i] << endl;
        if(s[i] != s[(s.size()-2)/2 - i]){
            cout << "No" << endl;
            return 0;
        }
    }

    for(int i = 0;i <= (s.size()-1)/4;i++){
        // cout << s[i + (s.size()+2)/2] << " e " <<  s[s.size()-1 - i] << endl;
        if(s[i + (s.size()+2)/2] != s[s.size()-1 - i]){
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 256
from math import log2
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = [[a[i]] for i in range(n)]
c = list(a)

for i in range(n-1):
    for j in range(i+1, n):
        b[i].append(a[j]+b[i][-1])
        c.append(b[i][-1])

m = 40 #ceil(log2((10**9)*1000))=40よりbit幅を40としておけば十分
ans = 0
for i in range(m, -1, -1):
    log = 2**i
    tmp = [x for x in c if x&log==log]
    if len(tmp) >= k:
        ans += log
        c = tmp
print(ans)


Measured memory_bytes: 31972
#include <stdio.h>

int search(int key, int n, int array[])
{
  int left, right, mid;
  left = 0;
  right = n;
  while (left < right) {
    mid = (left + right) / 2;
    if (array[mid] == key)     return 1;
    else if (array[mid] > key) right = mid;
    else                       left = mid + 1;
  }
  return 0;
}

int main(void)
{
  int n, s[100000];
  int q, t[50000];
  int i, count = 0;

  scanf("%d", &n);
  for (i = 0; i < n; i++) scanf("%d", &s[i]);
  scanf("%d", &q);
  for (i = 0; i < q; i++) scanf("%d", &t[i]);

  for (i = 0; i < q; i++) {
    if (search(t[i], n, s)) count++;
  }
  printf("%d\n", count);

  return 0;
}

Measured memory_bytes: 1184
#include <stdio.h>

int main(void) {
	int H, W;
	char a[128][128];
	char bei[128] = {0}, bej[128] = {0};
	int i, j;
	if (scanf("%d%d", &H, &W) != 2) return 1;
	for (i = 0; i < H; i++) {
		if (scanf("%127s", a[i]) != 1) return 1;
		for (j = 0; j < W; j++) {
			if (a[i][j] == '#') bei[i] = bej[j] = 1;
		}
	}
	for (i = 0; i < H; i++) {
		int kitaeri = 0;
		for (j = 0; j < W; j++) {
			if (bei[i] && bej[j]) {
				putchar(a[i][j]);
				kitaeri = 1;
			}
		}
		if (kitaeri) putchar('\n');
	}
	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define all(v) v.begin(), v.end()
#define ll long long
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<long long>;
using vvll = vector<vll>;

//snippets:tmp,cl,cvl,cs,co,coy,con,cov

const int mod=1e9+7;

int main(){
    ll n;
    cin >> n;
    ll k;
    cin >> k;
    ll count=0;
    repi(i,k,n+2){
        count+=i*(n+1-i)+1;
    }
    cout<<count%mod<<endl;
}

Measured memory_bytes: 3676
#!/usr/bin/env python3

def main():
    N = int(input())
    L = sorted(map(int, input().split()), reverse=True)
    ans = 0
    for i in range(N - 2):
        for j in range(i + 1, N - 1):
            for k in range(j + 1, N):
                if L[i] != L[j] and L[i] != L[k] and L[j] != L[k]:
                    if L[i] < L[j] +L[k]:
                        ans += 1
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 9156
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define print(x)cout<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;

const int mod = 1000000007;
struct mint {
  ll x;  // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod - a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res += a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res -= a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res *= a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod - 2); }
  mint& operator/=(const mint a) { return (*this) *= a.inv(); }
  mint operator/(const mint a) const {
    mint res(*this);
    return res /= a;
  }
};

int main() {
  int n,k;
  cin >> n >> k;
  vl a(n);
  int cnt = 0;
  int zero = 0;
  rep(i,n){
    cin >> a[i];
    cnt+= (a[i]>0);
    zero+=(a[i] == 0);
  }
  mint ans = 1;
  int l = 0, r = n-1;
  sort(rng(a));
  if(cnt == 0){
    if(k%2 == 0){
      rep(i,k)ans*=a[i];
    }
    else{
      rep(i,k)ans*=a[n-1-i];
    }
    cout<<ans.x<<endl;
    return 0;
  }
  else{
    while(k>1){
      if(a[l]*a[l+1] < a[r]*a[r-1]){
        ans*=a[r];
        ans*=a[r-1];
        r-=2;
      }
      else{
        ans*= a[l];
        ans*= a[l+1];
        l+=2;
      }
      k-=2;
    }
  }
  if(k == 1)ans*=a[r];
  cout<<ans.x<<endl;
  return 0;
}

Measured memory_bytes: 4824
import math
import sys

a, b, c = map(int, input().split())
if (a == b == c):
    if (a % 2 == 0):
        print(-1)
        sys.exit()
    else:
        print(0)
        sys.exit()

cnt = 0
while(True):
    half_a, half_b, half_c = a / 2, b / 2, c / 2
    ea = a % 2 == 0
    eb = b % 2 == 0
    ec = c % 2 == 0
    if (ea and eb and ec or (not ea) and (not eb) and (not ec)):
        cnt += 1
        a = half_b + half_c
        b = half_a + half_c
        c = half_a + half_b
    else:
        break

print(cnt)


Measured memory_bytes: 3316
#include<bits/stdc++.h>
using namespace std;
int main(){
 int A,B,C,D;
  cin >> A >> B >> C >> D ;
  if(A+B > C+D ){
    cout << "Left" << endl;
  }
  if(A+B == C+D){
  cout << "Balanced" << endl;
  }
  if(A+B < C+D ){
  cout << "Right" << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using lint = long int;
using llint = long long int;
using namespace std;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int count[26]{0};
    string s;
    while (cin >> s) {
        for (auto ch : s) {
            if ('a' <= ch && ch <= 'z') {
                count[ch - 'a'] += 1;
            } else if ('A' <= ch && ch <= 'Z') {
                count[ch - 'A'] += 1;
            }
        }
    }

    for (int i = 0; i < 26; i++) {
        cout << (char)('a' + i) << " : " << count[i] << endl;
    }
}



Measured memory_bytes: 3192
/**
 *    Author: Sutlan Ahmed
**/
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,sum=0,num=0,x;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d",&x);
        sum+=x;
        if(num<x)num = x;
    }
    sum -= num;
    sum += num/2;
    printf("%d\n",sum);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

int main()
{
	int p, q;

	while (cin >> p >> q ){
		string res = "";
		bool found = false;
		rep (i, 800 ){
			int r = 10*p/q;
			res += r + '0';
			if (10*p % q == 0 ){
				found = true;
				break;
			} // end if
			p = 10*p % q;
		} // end rep
		if (found ){
			cout << res << endl;
		}else{
			int sp = 0, ep = 0;
			string s = "", t = "";
			for (int i = 0; i < res.size(); i++ ){ // ツ開ツ始ツ暗環置
				bool same;			
				for (int l = 1; l <= 80; l++ ){
					same = true;
					s = res.substr (i, l );
					int cnt = 0;
					for (int j = i+l; j < res.size() && same; j += l ){
						t = res.substr (j, l );
						if (s == t ){
							cnt++;
						}else{
							same = false;
						} // end if
						if (cnt > 8 )
							break;
					} // end for
					if (same ){
						sp = i, ep = i+l;
						break;
					} // end if
				} // end for
				if (same )
					break;
			} // end for
			cout << res.substr (0, sp );
			cout << res.substr (sp, ep - sp ) << endl;
			cout << string (sp, ' ');
			cout << string (ep -sp ,'^') << endl;
		} // end if  
	} // end loop

		
	return 0;
}

Measured memory_bytes: 0
N = int(input())
L = list(map(str,input().split()))
flag = 4
if "P" in L :
    flag -= 1
if "W" in L :
    flag -= 1
if "G" in L :
    flag -= 1
if "Y" in L :
    flag -= 1
if flag == 0 :
    print("Four")
else :
    print("Three")
    
    

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
struct SCC{
  int n;
  vector<vector<int> > G,rG,T,C;
  vector<int> vs,used,belong;
  SCC(){}
  SCC(int sz):n(sz),G(sz),rG(sz),used(sz),belong(sz){}
  
  void add_edge(int from,int to){
    G[from].push_back(to);
    rG[to].push_back(from);
  }
  
  void input(int m,int offset=0){
    int a,b;
    for(int i=0;i<m;i++){
      cin>>a>>b;
      add_edge(a+offset,b+offset);
    }
  }
  
  void dfs(int v){
    used[v]=1;
    for(int i=0;i<(int)G[v].size();i++){
      if(!used[G[v][i]]) dfs(G[v][i]);
    }
    vs.push_back(v);
  }
  
  void rdfs(int v,int k){
    used[v]=1;
    belong[v]=k;
    C[k].push_back(v);
    for(int i=0;i<(int)rG[v].size();i++){
      if(!used[rG[v][i]]) rdfs(rG[v][i],k);
    }
  }
  
  int build(){
    fill(used.begin(),used.end(),0);
    vs.clear();
    for(int v=0;v<n;v++){
      if(!used[v]) dfs(v);
    }
    fill(used.begin(),used.end(),0);
    int k=0;
    for(int i=vs.size()-1;i>=0;i--){
      if(!used[vs[i]]){
	T.push_back(vector<int>());
	C.push_back(vector<int>());
	rdfs(vs[i],k++);
      }
    }
    for(int i=0;i<n;i++)
      for(int u:G[i])
	if(belong[i]!=belong[u])
	  T[belong[i]].push_back(belong[u]);
    for(int i=0;i<k;i++){
      sort(T[i].begin(),T[i].end());
      T[i].erase(unique(T[i].begin(),T[i].end()),T[i].end());
    }
    return k;
  }
};
signed main(){
  int n,m;
  cin>>n>>m;
  int V = n*2;
  vector<vector<int> > G(V);
  
  int l=0,r=n;
  for(int i=0;i<m;i++){
    int x,y;
    string s,t,u;
    cin>>x>>s>>u>>y>>t;
    x--;y--;
    if(s=="right") x+=n;
    if(t=="right") y+=n;
    G[x].emplace_back((y+n)%V);
    G[y].emplace_back((x+n)%V);
  }
  
  auto check=[&](int x)->int{
    SCC scc(V);
    for(int i=0;i<x;i++)
      for(int v=i;v<V;v+=n)
	for(int u:G[v])
	  if(u%n<x) scc.add_edge(v,u);
    
    scc.build();
    for(int i=0;i<x;i++)
      if(scc.belong[i]==scc.belong[i+n]) return 0;
    return 1;
  };
  
  while(l+1<r){
    int m=(l+r)>>1;
    if(check(m)) l=m;
    else r=m;
  }
  cout<<r<<endl;
  return 0;
}




Measured memory_bytes: 8060
#include <bits/stdc++.h>

using namespace std;


int N,A,B,C;
vector<int> l(8);


int dps(int i, int a, int b, int c){
    
    if (i == N) {
        if (a*b*c != 0) {
            return abs(A-a)+abs(B-b)+abs(C-c)-30;
            
        }else{

            return 88000;
        }
        
    }else{
        return min(min(dps(i+1, a, b, c), dps(i+1, a+l[i], b, c)+10), min(dps(i+1, a, b+l[i], c)+10, dps(i+1, a, b, c+l[i])+10));
    }
    
    
    
    
}



int main(){
    
    cin >> N >> A >> B >> C;
    
    for (int i = 0; i < N; i++) {
        cin >> l[i];
    }
    
    cout << dps(0, 0, 0, 0) << endl;;
    
    
}



Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    int n,c=0;
    scanf("%d",&n);
    int a[n];
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<n-1;i++){
        if(a[i-1]>a[i] && a[i]>a[i+1]){
            c++;
        }
        else if(a[i-1]<a[i] && a[i]<a[i+1]){
            c++;
        }
    }
    printf("%d\n",c);
    return 0;
}


Measured memory_bytes: 1724
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
  int N;
  cin >> N;
  vector<int> vec(N);
  for (int i=0;i<N;i++){
    cin  >> vec.at(i);
  }
  
  sort(vec.begin(),vec.end());
  int ans =0;
  for(int i=0;i<vec.at(N-1)+1;i++){
    if(vec.at((N-2)/2) < i && i <= vec.at(N/2)){
      ans++;
    }
  }
       
  
  
    cout << ans << endl;
    
    return 0;
  
}
    

Measured memory_bytes: 640
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
	int x = sc.nextInt();
    int a = sc.nextInt();
    int b = sc.nextInt();
    x-=a;
    x-=b*(x/b);
    System.out.println(x);
  }
}

Measured memory_bytes: 22996
#include <stdio.h>
#include <math.h>

#define PI 3.14159265358979323846264338327950L

int main(void) {
    int a, b, h, m;
    scanf("%d%d%d%d", &a, &b, &h, &m);
    long double rad = PI * 2 * ((long double)h / 12.0 + ((long double)m / 60.0) / 12.0 - (long double)m / 60.0);
    long double rsq = (long double)(a * a + b * b) - (long double)(2 * a * b) * cosl(rad);
    printf("%20.20Lf\n", sqrtl(rsq));
    
    return 0;
}

Measured memory_bytes: 2500
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)n; i++)

const double eps = 1e-10;

struct Point {
  double x, y;
  Point(double x = 0.0, double y = 0.0) : x(x), y(y) {}  
  double norm() {return sqrt(x*x + y*y);}
};

Point operator + (const Point &p, const Point &q) {return Point(p.x + q.x, p.y + q.y);}
Point operator - (const Point &p, const Point &q) {return Point(p.x - q.x, p.y - q.y);}
double operator * (const Point &p, const Point q) {return p.x * q.x + p.y * q.y;}
bool operator == (const Point &p, const Point &q) {return (abs(p.x - q.x) < eps && abs(p.y - q.y) < eps);}
bool operator != (const Point &p, const Point &q) {return !(p == q);}
double cross(const Point &p, const Point &q) {return p.x*q.y - p.y*q.x;}

struct Line_Segment {
  Point p , q;
  Line_Segment(Point p = Point(0.0,0.0), Point q = Point(0.0,0.0)) : p(p), q(q) {}
};

struct Line {
  double a, b, c;
  Line(double a, double b, double c) : a(a), b(b), c(c) {}
  Line(Point p, Point q) {
    a = q.y - p.y;
    b = p.x - q.x;
    c = q.x * p.y - p.x * q.y;
  }
};

struct Circle {
  double r;
  Point p;
  Circle(Point p = Point(0.0, 0.0), double r = 0.0) : p(p), r(r) {}
};

// 点と直線の距離
double point_line_dist(Point p, Line l) {
  return abs(l.a*p.x + l.b*p.y + l.c) / sqrt(l.a*l.a + l.b*l.b);
}

// 点の直線への射影
Point projection (Point p, Line l) {
  double x = p.x - l.a * (l.a*p.x + l.b*p.y + l.c) / (l.a*l.a + l.b*l.b);
  double y = p.y - l.b * (l.a*p.x + l.b*p.y + l.c) / (l.a*l.a + l.b*l.b);
  return Point(x,y);
}

// 点の線分からの回転方向
int ccw(Point p, Point p1, Point p2) {
  p1 = p1 - p; p2 = p2 - p;
  if(cross(p1,p2) > eps) return 1; 
  if(cross(p1,p2) < -eps) return -1; 
  if(p1 * p2 < 0) return 2; 
  if(p1.norm() < p2.norm()) return -2; 
  return 0; 
}

// 円と直線の交点
vector<Point> circle_line_cross(Line l, Circle c) {
  vector<Point> vp;
  Point h;
  h.x = c.p.x - l.a * (l.a*c.p.x + l.b*c.p.y + l.c) / (l.a*l.a + l.b*l.b);
  h.y = c.p.y - l.b * (l.a*c.p.x + l.b*c.p.y + l.c) / (l.a*l.a + l.b*l.b);

  double d = l.a*c.p.x + l.b*c.p.y + l.c;
  double q = c.r*c.r - d*d / (l.a*l.a + l.b*l.b);
  if(q >= eps) {
    Point p1, p2;
    p1.x = h.x + sqrt(q) * l.b / sqrt(l.a*l.a + l.b*l.b);
    p1.y = h.y - sqrt(q) * l.a / sqrt(l.a*l.a + l.b*l.b);
    p2.x = h.x - sqrt(q) * l.b / sqrt(l.a*l.a + l.b*l.b);
    p2.y = h.y + sqrt(q) * l.a / sqrt(l.a*l.a + l.b*l.b);
    vp.push_back(p1);
    vp.push_back(p2);
  } else if(abs(q) < eps) {
    vp.push_back(h);
  }
  return vp;
} 

// 線分の交差判定
bool line_segment_cross(const Line_Segment l, const Line_Segment s) {
  return ccw(l.p,l.q,s.p) * ccw(l.p,l.q,s.q) <= 0 && ccw(s.p,s.q,l.p) * ccw(s.p,s.q,l.q) <= 0;
}

int main() {
  Point p1, p2;
  cin >> p1.x >> p1.y >> p2.x >> p2.y;
  Line l(p1,p2);
  int q;
  cin >> q;
  rep(i,q) {
    Point p;
    cin >> p.x >> p.y;
    Point h = projection(p,l);
    printf("%.9lf %.9lf\n",h.x,h.y);
  }
  return 0;
}






Measured memory_bytes: 3292
from heapq import heappush, heappop
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
class UnionFind():
    def __init__(self, n):
        self.par = [-1 for i in range(n)]

    def root(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.root(self.par[x]) # contraction
            return self.par[x]

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            if self.par[x] > self.par[y]: # merge technique
                x, y = y, x
            self.par[x] += self.par[y]
            self.par[y] = x

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def size(self, x):
        return -self.par[self.root(x)]

n = int(input())
points = []
for i in range(n):
    x, y = map(int, input().split())
    points.append([x, y, i])

edge = []
points.sort()
for i in range(1, n):
    dist = points[i][0] - points[i-1][0]
    edge.append((points[i][2], points[i-1][2], dist))
    edge.append((points[i-1][2], points[i][2], dist))

points.sort(key=lambda x: x[1])
for i in range(1, n):
    dist = points[i][1] - points[i-1][1]
    edge.append((points[i][2], points[i-1][2], dist))
    edge.append((points[i-1][2], points[i][2], dist))

# print(edge)
edge.sort(key=lambda x: x[2])
uf = UnionFind(n)
ans = 0
for u, v, cost in edge:
    if not uf.same(u, v):
        ans += cost
        uf.unite(u, v)
print(ans)


Measured memory_bytes: 121856
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef unsigned long long int ulli;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define YN(x) cout<<(bool x?"Yes":"No")<<endl;
#define out(s) cout<<s<<endl;
#define pb push_back;
#define sp " ";
void vout(vector<int> v){
    for(int i=0;i<v.size();i++)
    cout<<v.at(i)<<endl;
}
int main(){
    string s,t,u;
    int a,b;
    cin>>s>>t>>a>>b>>u;
    (s==u?a-=1:b-=1);
    cout<<a<<" "<<b;
}

Measured memory_bytes: 256
k, n = input("").split()
k = int(k)
n = int(n)
Loc = list(map(int, input("").split()))
temp = Loc[-1]-Loc[0]
for i in range(n-1):
    x1 = Loc[i-1] + k - Loc[i]
    x2 = Loc[i] + k - Loc[i+1]
    temp = min(temp, x1, x2)
temp = min(temp,Loc[-1]-Loc[0], Loc[-2]+k-Loc[-1])

print(temp)

Measured memory_bytes: 26444
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include <queue>
#include <utility>
#include <map>
#include <set>
#include <deque>
using namespace std;

int main() {
    
    int N,A,B;
    cin >> N >> A >> B;

    cout << min(N*A,B) << endl;

    return 0;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
using i64 = long long;

const i64 MOD = 1e9 + 7;

int main()
{
  i64 n, m;
  cin >> n >> m;
  vector<i64> dp(n + 1, 0);
  for (i64 i = 0; i < m; i++)
  {
    i64 a;
    cin >> a;
    dp[a] = -1;
  }
  dp[0] = 1;
  for (i64 i = 0; i < n; i++)
    if (dp[i] != -1)
      for (i64 j = 1; j <= 2; j++)
      {
        if (n < i + j)
          break;
        if (dp[i + j] == -1)
          continue;
        (dp[i + j] += dp[i]) %= MOD;
      }
  cout << dp[n] % MOD << endl;
  return 0;
}


Measured memory_bytes: 1024
#include "bits/stdc++.h"
using namespace std;

int main(){

string s,t;
int a,b;
string u;
  
  cin>>s>>t;
  cin>>a>>b;
  cin>>u;
  
if(s==u){
  a--;
  
}
else if(t==u)
  b--;
  
cout<< a<<" "<<b; 
  


}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	N, K := ReadInt(), ReadInt()
	A := ReadInts(N)

	for k := 0; k < K; k++ {
		next := make([]int, N)
		for i := 0; i < N; i++ {
			l := i - A[i]
			r := i + A[i] + 1
			if l < 0 {
				l = 0
			}
			next[l]++
			if r <= N-1 {
				next[r]--
			}
		}
		for i := 0; i < N-1; i++ {
			next[i+1] += next[i]
		}
		A = next
		c := 0
		for i := 0; i < N; i++ {
			if A[i] == N {
				c++
			}
		}
		if c == N {
			break
		}
	}
	for i := 0; i < N; i++ {
		fmt.Printf("%d ", A[i])
	}
	fmt.Println()
}

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt() (i int)       { Scan(&i); return }
func ReadString() (s string) { Scan(&s); return }
func ReadInts(n int) []int {
	v := make([]int, n)
	for i := 0; i < n; i++ {
		Scan(&v[i])
	}
	return v
}


Measured memory_bytes: 10080
#include <stdio.h>
int a,b;
char op;
int ans;


main(){
  while(1){
  scanf("%d %c %d",&a,&op,&b);
  if(op=='+'){
   ans=a+b;
    printf("%d\n",ans);
    ans=0;
    }

  else if(op=='-'){
   ans=a-b;
    printf("%d\n",ans);
   ans=0;
    }

   else if(op=='*'){
   ans=a*b;
    printf("%d\n",ans);
    ans=0;
    }
    
   else if(op=='/'){
   ans=a/b;
    printf("%d\n",ans);
    ans=0;
   }

  else{
  return 0;
  }
  }
}
 

Measured memory_bytes: 600
#include<bits/stdc++.h>
using namespace std;

int main()
{
  
  string s;
  cin>>s;
   string arr[3]={"Sunny", "Cloudy", "Rainy"};
  for(int i=0;i<3;i++)
  {
  if(s == arr[i])
  {
    cout<<arr[(i+1)%3]<<endl;
    return 0;
  }
  }
}

Measured memory_bytes: 256
using System;
using System.Linq;
using System.Collections.Generic;
using System.Text;
using static System.Console;
using static System.Math;

class Program
{
    static void Main(string[] args)
    {
        solve();
    }
    static int N;
    static int[] A;
    static void input()
    {
        N = int.Parse(ReadLine());
        A = new int[N + 1];
        int[] tmp = ReadLineParseIntArray();
        for(int i = 0; i < N; i++)
        {
            A[i + 1] = tmp[i];
        }
    }
    static void solve()
    {
        input();
        int[] ans = new int[N + 1];
        int ballCount = 0;
        for(int i = N; i >= 1; i--)
        {
            int c = 0;
            if (2 * i <= N)
            {
                for (int j = 2 * i; j <= N; j += i)
                {
                    c += ans[j];
                }
            }
            ans[i] = (c + A[i]) % 2;
            if (ans[i] == 1)
                ballCount++;
        }
        WriteLine(ballCount);
        int k = 1;
        for(; k < N; k++)
        {
            if (ans[k] == 1)
            {
                Write(k);
                k++;
                break;
                
            }      
        }
        for(; k <= N; k++)
        {
            if (ans[k] == 1)
                Write(" " + k);
        }
        WriteLine();
    }
    static int ReadLineParseInt() => int.Parse(ReadLine());
    static int[] ReadLineParseIntArray() => ReadLine().Split(' ').Select(int.Parse).ToArray();
}

Measured memory_bytes: 31060
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int N;
    cin >> N;
    vector<int> a(N);
    for (int i = 0; i < N; i++) cin >> a[i];

    sort(a.begin(), a.end());

    int left = 0, right = 0;
    int count = 1;
    while (right < N-1) {
        if (a[right+1] - a[left] <= 2) {
            right++;
        } else {
            left++;
        }
        count = max(count, right-left+1);
    }

    cout << count << endl;
}

Measured memory_bytes: 640