akhauriyash/Code-Regression huggingface dataset:
N = int(input())
ans  = 10**5+1
for i in range(1,N//2 + 1):
    A = i
    B = N - i
    tmp = 0
    while(A > 0):
        tmp += A % 10
        A //= 10
    while(B > 0):
        tmp += B % 10
        B //= 10
    ans = min(ans,tmp)
print(str(ans))

Measured memory_bytes: 9084
/*===============================================================
*  Filename：C.cpp
*  Author：zhuyutian
*  Date：2018年01月21日
================================================================*/
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int maxn = 100005;

int n;

int main()
{
    //freopen("C.in","r",stdin);
    //freopen("C.out","w",stdout);
	scanf("%d",&n);
	bool ok = true;
	int x = 0,y = 0,now = 0;
	for(int i = 0; i < n; i++)
	{
		int t,a,b;
		scanf("%d%d%d",&t,&a,&b);
		int dist = abs(x - a) + abs(y - b);
		int time = t - now;
		if(time < dist) ok = false;
		else if((time - dist) % 2) ok = false;
		x = a; y = b;
		now = t;
	}
	puts(ok ? "Yes" : "No");
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	static int h, w, c;
	static int a[][];
	static int dx[] = {-1, 0, 0, 1};
	static int dy[] = {0, -1, 1, 0};
	
	public static int f(int k) {
		int b[][] = new int[h][w];
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				b[i][j] = a[i][j];
			}
		}
		
		if (k == 6) {
			int cnt = count(c, 0, 0);
			for (int i = 0; i < h; i++) {
				for (int j = 0; j < w; j++) {
					a[i][j] = b[i][j];
				}
			}
			return cnt;
		}
		
		int max = 0;
		for (int q = 1; q <= 6; q++) {
			for (int i = 0; i < h; i++) {
				for (int j = 0; j < w; j++) {
					a[i][j] = b[i][j];
				}
			}
			if (q != a[0][0]) {
				change(b, q, 0, 0);
				max = Math.max(max, f(k + 1));
			}
		}
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				a[i][j] = b[i][j];
			}
		}
		return max;
	}
	
	public static void change(int b[][], int c, int x, int y) {
		int k = b[0][0];
		a[y][x] = c;
		for (int i = 0; i < 4; i++) {
			if (0 <= x + dx[i] && x + dx[i] < w && 0 <= y + dy[i] && y + dy[i] < h) {
				if (a[y + dy[i]][x + dx[i]] == k) {
					change(b, c, x + dx[i], y + dy[i]);
				}
			}
		}
	}
	
	public static int count(int k, int x, int y) {
		int cnt = 1;
		a[y][x] = -1;
		for (int i = 0; i < 4; i++) {
			if (0 <= x + dx[i] && x + dx[i] < w && 0 <= y + dy[i] && y + dy[i] < h) {
				if (a[y + dy[i]][x + dx[i]] == k) {
					cnt += count(k, x + dx[i], y + dy[i]);
				}
			}
		}
		return cnt;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (true) {
			h = sc.nextInt();
			w = sc.nextInt();
			c = sc.nextInt();
			if ((h | w | c) == 0) {
				break;
			}
			
			a = new int[h][w];
			for (int i = 0; i < h; i++) {
				for (int j = 0; j < w; j++) {
					a[i][j] = sc.nextInt();
				}
			}
			System.out.println(f(1));
		}
	}
}

Measured memory_bytes: 162176
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using namespace std;
template <class T> void setmax(T & a, T const & b) { if (a < b) a = b; }
const int inf = 1e9+7;
int main() {
    int n; cin >> n;
    vector<vector<int> > g(n);
    repeat (i, n-1) {
        int a, b; cin >> a >> b; -- a; -- b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int k; cin >> k;
    vector<int> l(n, - inf), r(n, inf); // [l, r)
    repeat (i, k) {
        int v, p; cin >> v >> p; -- v;
        l[v] = p;
        r[v] = p+1;
    }
    const int root = 0;
    function<bool (int, int)> go1 = [&](int i, int parent) {
        vector<int> ls, rs;
        ls.push_back(l[i]);
        rs.push_back(r[i]);
        for (int j : g[i]) if (j != parent) {
            if (not go1(j, i)) return false;
            ls.push_back(max(- inf, l[j] - 1));
            rs.push_back(min(  inf, r[j] + 1));
        }
        l[i] = *whole(max_element, ls); for (int lj : ls) if (lj != - inf and lj % 2 != l[i] % 2) return false;
        r[i] = *whole(min_element, rs); for (int rj : rs) if (rj !=   inf and rj % 2 != r[i] % 2) return false;
        if (r[i] - l[i] <= 0) return false;
        return true;
    };
    bool possible = go1(root, -1);
    cout << (possible ? "Yes" : "No") << endl;
    if (possible) {
        vector<int> result(n, - inf);
        function<void (int, int)> go2 = [&](int i, int parent) {
            result[i] = l[i];
            for (int j : g[i]) if (j != parent) {
                setmax(l[j], l[i] - 1);
                go2(j, i);
            }
        };
        go2(root, -1);
        for (int it : result) cout << it << endl;
    }
    return 0;
}


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

int man = 10000;
int gosen = 5000;
int sen = 1000;

int main() {
    bool is_equal = false;

    int n, y;
    cin >> n >> y;
    int mani, goi, sei;
    for (mani=0; mani<=n; mani++) {
        for (goi=0; goi<=n-mani; goi++) {
            int total = mani*man + goi*gosen;
            int rest = y - total;
            if (rest < 0) break;
            sei = rest / sen;
            int counts = mani + goi + sei;
            if (counts > n) continue;
            if (rest % sen == 0 && counts == n) {
                is_equal = true;
                break;
            }
        }
        if (is_equal) break;
    }
    if (is_equal) {
        cout << mani << ' ' << goi << ' ' << sei << endl;
    } else {
        cout << -1 << ' ' << -1 << ' ' << -1 << endl;
    }
    


}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)
const int mod = 1000000007;

int main(){
  int n;
  cin >> n;
  vector<int> x(n);
  rep (i, n) cin >> x[i];
  ll ans = LLONG_MAX;
  for (int i = 1; i <= 101; ++i) {
    ll cost = 0;
    rep (j, n) {
      cost += pow(x[j] - i, 2); 
    }
    ans = min(ans, cost);
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <map>
#include <queue>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int MOD = 1000000007;
const int iINF = 1001001001;
const long long llINF = 1LL << 60;
ll g1(ll n, ll p)
{
	if (n == 0)	return 0;
	return n / p + g1(n / p, p);
}
ll g2(ll n, ll p)
{
	if (n % 2 == 1) {
		return g1(n, p) - g2(n - 1, p);
	}
	ll ret = g1(n / 2, p);
	if (p == 2)	ret += n / 2;
	return ret;
}
int main()
{
	ll n = 0;
	cin >> n;
	if (n % 2 == 1) {
		cout << 0 << endl;
		return 0;
	}
	ll ans = min(g2(n, 2), g2(n, 5));
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 3608
package main

import (
	"fmt"
	"sort"
)

func main() {
	var k, n int
	fmt.Scan(&n, &k)
	p := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&p[i])
	}
	sort.Ints(p)
	ans := 0
	for i := 0; i < k; i++ {
		ans += p[i]
	}
	fmt.Print(ans)
}


Measured memory_bytes: 1888
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std;

typedef long long ll;

int dp[3010][3010];

int main() {
  string s,t;
  cin >> s >> t;
  string ans="";
  for ( int i = 0;i < s.length(); i++ ) {
    for ( int j = 0; j < t.length(); j++ ) {
      if ( s[i] == t[j] ) {
	dp[i+1][j+1] = dp[i][j] + 1;
      } else {
	dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1]);
      }
    }
  }

  /*
  int i = s.length(),j = t.length();
  while( i > 0 && j > 0 ) {
    if ( dp[i][j] == dp[i-1][j] ) {
      i--;
    }else if ( dp[i][j] == dp[i][j-1] ) {
      j--;
    }else {
      ans+=s[i-1];
      i--;
      j--;
    }
  }
  */
    int i = s.length(),j = t.length();
  while( i > 0 && j > 0 ) {
    if ( dp[i][j] == dp[i][j-1] ) {
      j--;
    }else if ( dp[i][j] == dp[i-1][j] ) {
      i--;
    }else {
      ans+=s[i-1];
      i--;
      j--;
    }
  }
  reverse(ans.begin(),ans.end());
  /* for ( int i= 0; i <= s.length(); i++ ) {
    for ( int j = 0; j <= t.length(); j++ ) {
      cout << dp[i][j] << " ";
    }
    cout << endl;
  }
  */
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 35584
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    return

#B
def B():
    return

#C
def C():
    n = II()
    xyh = LIR(n)
    xyh.sort(key = lambda x:x[2], reverse = True)
    x1, y1, h1 = xyh[0]
    del xyh[0]
    for x in range(101):
        for y in range(101):
            h = abs(x - x1) + abs(y - y1) + h1
            flg = True
            for xn, yn, hn in xyh:
                if max(h - abs(x - xn) - abs(y - yn), 0) == hn:
                    continue
                flg = False
                break
            if flg:
                print(x, y, h)
                return 
    return

#D
def D():
    n, m = LI()
    ans = 1
    for i in range(1,int(math.sqrt(m)+1)):
        if m % i == 0:
            a = m // i
            #print(i,a)
            if a * n <= m:
                ans = max(ans, a)
            if i * n <= m:
                ans = max(ans, i)
    print(ans)
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    D()


Measured memory_bytes: 39024
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,k;
	cin >> n >> k;
	int arr[n+1];
	for(int i=1;i<=n;i++){
		cin >> arr[i];
	}
	vector<bool> dp(k+1);//dp[i] = true if we have i stones and first player to move wins
	for(int i=0;i<=k;i++){
		for(int j=1;j<=n;j++){
			if(i-arr[j] >= 0 && !dp[i-arr[j]])
				dp[i] = true;
		}
	}
	if(dp[k])
		cout << "First\n";
	else
		cout << "Second\n";
}

Measured memory_bytes: 3612
x = int(input())
flag = False
for i in range(x, 1000000):
    for j in range(2, i+1):
        #print(i, j)
        if j == i:
            print(i)
            flag = True
            break
        if i % j == 0:
            #print('*', i, j)
            break
    if flag:
        break

Measured memory_bytes: 9084
#include<iostream>
#include<map>
#include<string>

int main(){
    int n;
    std::cin >> n;
    
    std::map<std::string, int> mp;
    for(int i = 0; i < n; i++){
        std::string s;
        std::string x;
        std::cin >> s >> x;
        
        if(s == "insert") mp[x]++;
        else if(s == "find"){
            if(mp.count(x)) std::cout << "yes" << std::endl;
            else std::cout << "no" << std::endl;
        }
    }
    return 0;
}


Measured memory_bytes: 36428
#include<iostream>
using namespace std;
int main(){
	int n,a,b;
	cin>>n>>a>>b;
	int ar[n+10];
	int x,s=0;
	for(int i=1;i<=n;i++){
		cin>>x;
		if(x<a||x>=b) s++;
	}
	cout<<s<<endl;
	return 0;
}


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

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

	int ans = 0;
	for( int i = 0; i < N; i++ ) {
		if( V[i] - C[i] > 0 ) {
			ans += V[i] - C[i];
		}
	}

	cout << ans << endl;
 
	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"

#define rep(n) for(int i=0;i<n;i++)
#define ll long long
#define MAX 101
using namespace std;

double a(double v,int i){
    double s=v;
    for(int j=0;j<i;j++)s/=2;
  	
    return s;
}
int main(){
    int n ;
    double v[MAX],ans=0;
    cin>>n;
    rep(n)cin>>v[i];
    sort(v,v+n);
    rep(n){
        if(i==0)ans+=a(v[i],n-1);
        else ans+=a(v[i],n-i);
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
s=input()
N=len(s)
a="Yes"

for i in range (0,N):
  if i%2==0:
    if (s[i]!="R") and (s[i]!="U") and (s[i]!="D"):
      a="No"
      break
  else:
    if (s[i]!="L") and (s[i]!="U") and (s[i]!="D"):
      a="No"
      break
print(a)
      
      
      


Measured memory_bytes: 3060
#include <iostream>

using namespace std;

long long solve(long long n, long long m){
    if (n*2 >= m){
        return m/2;
    }
    m -= 2*n;
    m /= 4;
    /* cout << n << " " << m << endl; */
    return n + m;
}

int main(){
    long long n,m;
    cin >> n >> m;
    cout << solve(n,m) << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <iomanip>
#include <bitset>
#include <cassert>
using namespace std;
typedef long long ll;

ll mod = 998244353;
ll dp[4003][4003];
int nr[4003], nb[4003];

int main() {
	string s; cin >> s;
	int n = s.size();
	for (int i = 0; i < n; i++) {
		nr[i + 1] = nr[i] + 2 * (s[i] == '0') + (s[i] == '1');
		nb[i + 1] = nb[i] + 2 * (s[i] == '2') + (s[i] == '1');
	}
	for (int i = n; i <= 2 * n; i++) {
		nr[i + 1] = nr[i];
		nb[i + 1] = nb[i];
	}
	dp[0][0] = 1;
	for (int i = 0; i < 2*n; i++) {
		for (int j = 0; j <= min(i, nr[i]); j++) {
			if (nr[i + 1] - j > 0) dp[i + 1][j + 1] += dp[i][j], dp[i + 1][j + 1] %= mod;
			if (nb[i + 1] - (i - j) > 0) dp[i + 1][j] += dp[i][j], dp[i + 1][j] %= mod;
		}
	}
	cout << dp[2 * n][nr[2 * n]] << endl;
	return 0;
}


Measured memory_bytes: 123648
#include <iostream>

using namespace std;

int main() {
	int R;cin >> R;
	if (R < 1200) {
		cout << "ABC" << endl;
		return 0;
	}
	if (R < 2800) {
		cout << "ARC" << endl;
		return 0;
	}
	cout << "AGC" << endl;return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
const int INF = 1000000000; // 10^9
int main() {
    // ifstream in("data1.txt");
    // cin.rdbuf(in.rdbuf());
    ll N, K;
    cin >> N >> K;

    if(N % K == 0){
        cout << 0 << endl;
        return 0;
    }

    if(N < K){
        if(N < abs(N-K)){
            cout << N << endl;
        } else {
            cout << abs(N-K) << endl;
        }
        return 0;
    } else {
        ll x = N % K;
        if(x < abs(x-K)){
            cout << x << endl;
        } else {
            cout << abs(x-K) << endl;
        }
        return 0;
    }
}


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


using namespace std;

int main()
{
    string s , p ;
    cin >> s >> p ;
    int f = 0 ;
    for(int i=s.length()-1;i>=0;i--)
    {
        string c ;
        c = s[s.length()-1];
        if(s==p)
        {
            f = 1;
            break;
        }
        s.pop_back();
        s = c + s ;
    }
    f == 1? puts("Yes"):puts("No");
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <sstream>
#include <cmath>
#include <math.h>
#include <cstring>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <list>
#include <iomanip>
#include <numeric>
#include <utility>
#include <random>
#include <chrono>
#include <cstdlib>
#include <cstdio>
#include <functional>
#include <memory.h>
#include <cassert>
#include <complex>
#include <ctime>
#include <limits>

using namespace std;

using ll = long long;
using ld = long double;
using db = double;
using str = string;

using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>; 

using vi = vector<int>;
using vl = vector<long long>;
using vd = vector<double>;
using vs = vector<string>;
using vld = vector<long double>;
using vpi = vector<pair<int, int>>;
using vpl = vector<pair<long long, long long>>;
using vpd = vector<pair<double, double>>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<long long>>;

#define mp make_pair
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend() 
#define rs resize
#define ins insert 
#define ft front() 
#define bk back()
#define pf push_front 
#define pb push_back
#define eb emplace_back 
#define lb lower_bound 
#define ub upper_bound
#define nl "\n"
#define trav(i, x) for (auto& i: x)

const int MOD = 998244353;
const int MX = 5005;
const ll INF = 1e18; 
const ld PI = acos((ld)-1);
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 

ll lcm(ll a, ll b) { return (a / (__gcd(a, b)) * b); }
ll gcd(ll a,ll b) { return b ? gcd(b, a % b) : a; }
ll pow(ll a, ll b) { ll res = 1; while (b > 0) { if (b & 1) res = res * a; a = a * a; b >>= 1; } return res; }

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

	int a[5];
	for(int i = 0; i < 5; i++) {
		cin >> a[i];
		if(a[i] == 0) {
			cout << i + 1 << nl;
			break;
		}
	}
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<50;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};

int n,m,S;
vvi g;
vl a;

vl f(int v){
	vl dp(S);
	for(int i=0;i<S;i++) if(i&1<<v){
		int T=(i-1)&i;
		dp[i]=a[i];
		while(T){
			if(T&1<<v) dp[i]=(dp[i]-dp[T]*a[i-T]%mod+mod)%mod;
			T=(T-1)&i;
		}
	}
	return dp;
}

int main(){
	cin>>n>>m;
	g=vvi(n,vi(n));
	for(int i=0;i<m;i++){
		int u,v;
		cin>>u>>v;
		u--;v--;
		g[u][v]++;g[v][u]++;
	}
	S=1<<n;
	a=vl(S,1);
	for(int i=0;i<S;i++) for(int j=0;j<n;j++) for(int k=j+1;k<n;k++) if(i&1<<j&&i&1<<k&&g[j][k]) (a[i]*=2)%=mod;
	vl dp1=f(0),dp2=f(1);
	ll res=a[S-1];
	for(int i=1;i<S;i+=2) if(!(i&2)){
		int T=S-i-1;
		for(int j=0;j<n;j++) for(int k=0;k<n;k++) if(i&1<<j&&T&1<<k&&g[j][k]) T-=1<<k;
		int T_=T;
		while(T){
			if(T&2) res=(res-dp1[i]*dp2[T]%mod*a[S-i-T-1]%mod+mod)%mod;
			T=(T-1)&T_;
		}
	}
	cout<<res<<endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>

using namespace std;
#define PI acos(-1)

int main()
{
	string s;
	cin >> s;

	int j = 0;
	for (int i = 0; i < s.size(); i++) {
		if (
			s[i] == '1'){
			j++;
	}
}
	cout << j;
}



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

int main()
{
    int n,k;
    cin >> n >> k;
    vector<int> p(n);
    rep(i,n) cin >> p[i];

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

    int sum = 0;

    rep(i,k) {sum =sum + p[i];}

    cout << sum << endl;

    return 0;
}


Measured memory_bytes: 3572
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize(4)
//#pragma GCC optimize("unroll-loops")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
//#include <bits/extc++.h>
#define fi first
#define se second
#define db double
#define mp make_pair
#define pb push_back
#define mt make_tuple
//#define pi acos(-1.0)
#define ll long long
#define vi vector<int>
#define mod 998244353
#define ld long double
//#define C 0.5772156649
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define pii pair<int,int>
#define ull unsigned long long
#define bpc __builtin_popcount
#define base 1000000000000000000ll
#define fin freopen("a.txt","r",stdin)
#define fout freopen("a.txt","w",stdout)
#define fio ios::sync_with_stdio(false);cin.tie(0)
#define mr mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline void sub(ll &a,ll b){a-=b;if(a<0)a+=mod;}
inline void add(ll &a,ll b){a+=b;if(a>=mod)a-=mod;}
template<typename T>inline T const& MAX(T const &a,T const &b){return a>b?a:b;}
template<typename T>inline T const& MIN(T const &a,T const &b){return a<b?a:b;}
inline ll mul(ll a,ll b,ll c){return (a*b-(ll)((ld)a*b/c)*c+c)%c;}
inline ll qp(ll a,ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}
inline ll qp(ll a,ll b,ll c){ll ans=1;while(b){if(b&1)ans=mul(ans,a,c);a=mul(a,a,c),b>>=1;}return ans;}

using namespace std;
//using namespace __gnu_pbds;

const ld pi = acos(-1);
const ull ba=233;
const db eps=1e-5;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int N=200000+10,maxn=2000000+10,inf=0x3f3f3f3f;

char s[N];
int dp[N][2];
int main()
{
    scanf("%s",s+1);
    int n=strlen(s+1);
    memset(dp,-1,sizeof dp);
    dp[1][0]=1;
    dp[2][1]=1;
    for(int i=1;i<=n;i++)
    {
        if(~dp[i][0])
        {
            dp[i+2][1]=max(dp[i+2][1],dp[i][0]+1);
            if(s[i]!=s[i+1])
                dp[i+1][0]=max(dp[i+1][0],dp[i][0]+1);
        }
        if(~dp[i][1])
        {
            dp[i+1][0]=max(dp[i+1][0],dp[i][1]+1);
            if(s[i]==s[i+2]&&s[i-1]==s[i+1])continue;
            dp[i+2][1]=max(dp[i+2][1],dp[i][1]+1);
        }
    }
//    printf("%d\n",n);
    printf("%d\n",max(dp[n][0],dp[n][1]));
    return 0;
}
/********************

********************/


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

int main(){
    int n;
    cin >> n;
    int a[n];
    rep(i,n){
        int x;
        cin >> x;
        a[i] = x%2;
    }
    int sum = 1;
    rep(i,n){
        if(a[i]==0)sum*=2;
    }
    int allsum = pow(3,n);
    cout << allsum-sum << endl;

    return 0;
}


Measured memory_bytes: 256
#include<string>
#include<string.h>
#include<map>
#include<set>
#include<vector>
#include<stdio.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stdio.h>

using namespace std;




int main()
{
    int a,b,c,x,y,ans=0,cnt=0,sum=0,lk=0;
    cin>>a>>b>>c>>x>>y;
    if(2*c>(a+b))
    cout<<x*a+y*b;
    else
    {
        if(x>y)
        {
        cnt=2*y*c+(x-y)*a;
        ans=2*x*c;
        cout<<min(ans,cnt);
        }
        else if(x<y)
        {
        cnt=2*x*c+(y-x)*b;
        ans=2*y*c;
        cout<<min(ans,cnt);
        }
        else if(x==y)
        cout<<2*x*c;
    }
   // system("pause");
    return 0;
}  

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

int main(void)
{
    int A, B;
    cin >> A >> B;
    if (13 <= A) {
        cout << B << endl;
    }
    else if (A <= 5) {
        cout << 0 << endl;
    }
    else {
        cout << B / 2 << endl;
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;
typedef long long ll;

inline int R()
{
	int rt = 0;
	bool isn = false;
	char ch = getchar();
	for ( ; ch < '0' || ch > '9'; ch = getchar() )
		isn = ch == '-' ? true : isn;
	for ( ; ch >= '0' && ch <= '9'; ch = getchar() )
		rt = rt * 10 + ch - '0';
	return isn ? -rt : rt;
}

int main()
{
//	freopen ( "test.in", "r", stdin );
	ll n, s;
	scanf ( "%lld%lld", &n, &s );
	if ( n < s )
	{
		puts ( "-1" );
		return 0;
	}
	if ( n == s )
	{
		printf ( "%lld\n", n + 1 );
		return 0;
	}
	ll lm = sqrt ( n );
	for ( ll i = 2; i <= lm; ++i )
	{
		ll nans = 0;
		for ( ll na = n; na; na /= i )
			nans += na % i;
		if ( nans == s )
		{
			printf ( "%lld\n", i );
			return 0;
		}
	}
	for ( int i = lm; i; --i )
	{
		ll rem = n - s;
		if ( !( rem % i ) )
		{
			ll ans = rem / i + 1;
			ll nans = 0;
			for ( ll na = n; na; na /= ans )
				nans += na % ans;
			if ( nans != s )
				continue;
			printf ( "%lld\n", ans );
			return 0;
		}
	}
	puts ( "-1" );
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(void){
    float M,vote_i,vote_sum;
    int N, i = 0;

    cin >> N >> M;

    vector<float> A(N);
    for (i = 0; i < N; i++){
        cin >> vote_i;
        A.push_back(vote_i);
        vote_sum += vote_i;
    }

    sort(A.begin(),A.end(),greater<int>());


    for (i = 0; i < M; i++){
        if( A[i]  < ((vote_sum/(4*M))) ){
            cout << "No";
            return 0;
        }
    }

    cout << "Yes";
    return 0;
}

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

using namespace std;

typedef long long LL;
typedef long double LD;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<LD, LD> PLDLD;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define CLR(a) memset((a), 0 ,sizeof(a))
#define ALL(a) a.begin(),a.end()

const double eps=1e-5;
const long long INF=(LL)(1e9)*(LL)(1e9);



int main()
{
    //cin.tie(0);
    //ios::sync_with_stdio(false);
    int n,m;
    cin>>n;
    vector<int> d(n);
    REP(i,n)
        cin>>d[i];
    cin>>m;
    vector<int> t(m);
    REP(i,m)
        cin>>t[i];
    
    sort(ALL(d));
    sort(ALL(t));

    int k=0;
    bool flag=1;
    REP(i,m)
    {
        while(d[k]<t[i])
        {
            k++;
        }
        if(d[k]!=t[i])
        {
            flag=0;
            break;
        }
        k++;
    }
    if(flag)
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;
}

Measured memory_bytes: 1792
#include<iostream>
#include<string>

using namespace std;

int main(void){
  int N, K;
  cin >> N;
  string S;
  cin >> S;
  cin >> K;
  for(int i = 0; i < N; i++){
    if(S[i] != S[K - 1]) S[i] = '*';
  }
  cout << S << endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    long long int a,b,c,d;
    scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
    long long int ar[4];

    ar[0]=a*c;
    ar[1]=a*d;
    ar[2]=b*c;
    ar[3]=b*d;

    long long int i,max=ar[0];
    for(i=0; i<4; i++)
    {
        if(ar[i]>max)
            max=ar[i];
    }
    printf("%lld\n",max);

    return 0;

}


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

int main() {
    int N, K, a;
    cin >> N >> K;
    vector<long long> p(N + 1), s(N + 1);
    for (int i = 0; i < N; i++) {
        cin >> a;
        if (a > 0) {
            p.at(i + 1) = p.at(i) + a;
        } else {
            p.at(i + 1) = p.at(i);
        }
        s.at(i + 1) = s.at(i) + a;
    }
    long long ans = 0;
    for (int i = 0; i < N - K + 1; i++) {
        long long score = p.at(N) - p.at(K + i) + p.at(i) + max(s.at(K + i) - s.at(i), 0LL);
        ans = max(ans, score);
    }
    cout << ans << endl;
}

Measured memory_bytes: 1920
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.next());
        int flag = 0;
        for (int i=1;i<=9;i++) {
            if (1<=N/i && N/i<=9 && N%i==0) {
                flag=1;
                break;
            }
        }
        if (flag==1) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 23892
N = gets.to_i

s, i, b, h = [nil]*N+[0,1], -1, 0, [-2]*200001
until (i+=1) == N
	c = gets.to_i
	next s[i] = s[i-1] if b == c
	b, h[c], s[i] = c, i, (s[i-1] + s[h[c]]) % 1000000007
end
p s[N-1]


Measured memory_bytes: 6524
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
// #define int long long

template <class T>
bool INRANGE(T x, T a, T b) { return a <= x && x <= b; }
template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define RREP(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define RFOR(i, a, b) for (int i = (a); i >= (b); --i)
#define ALL(v) (v).begin(), (v).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
                      << " " << __FILE__ << endl;

typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<vi> vvi;
typedef pair<int, int> pii;

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

    vector<ll> x(2), y(2);

    cin >> x[0] >> x[1];
    cin >> y[0] >> y[1];

    ll ans = -1e18-5;
    REP(xi, 2) REP(yi, 2) {
        ans = max(x[xi]*y[yi], ans);
    }

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3648
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
using namespace std;
pair<long long, int> a[200000]; long long n, b[200000], t;
long long maximum_profit() {
	long long res = 0, r = 1LL << 31;
	for (int i = 0; i < n; i++) {
		res = max(res, b[i] - r);
		r = min(r, b[i]);
	}
	return res;
}
int main() {
	cin >> n >> t;
	for (int i = 0; i < n; i++) {
		cin >> b[i]; a[i] = make_pair(b[i], i);
	}
	sort(a, a + n); int J = maximum_profit();
	vector<int> t;
	for (int i = 0; i < n; i++) t.push_back(a[i].first);
	long long cnt = 0;
	for (int i = 0; i < n; i++) {
		int ptr = lower_bound(t.begin(), t.end(), t[i] + J) - t.begin();
		if (ptr < n && t[ptr] == t[i] + J && a[i].second < a[ptr].second) cnt++;
	}
	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 3196
#include <bits/stdc++.h>
using namespace std;
#define int long long

bool isprime(int n){
    double rootn = sqrt(n);
    if (n < 2){
        return false;
    }
    else if (n == 2){
        return true;
    }
    else if (n % 2 == 0){
        return false;
    }
    else{
        for(int i = 3; i <= rootn; i += 2){
            if(n % i == 0){
                return false;
            }
        }
        return true;
    }
}

// 空のベクトルを二つ渡す。N (>=2) 以下の素数を primes に順番に入れる。
void prime_vectors(int N, vector<int>& primes, vector<bool>& is_prime){
    primes = {};
    is_prime = {};
    for(int i=0; i<=N; i++){
        is_prime.push_back(true);
    }

    primes.push_back(2);
    for(int j=4; j<=N; j+=2){
        is_prime[j] = false;
    }

    int i;
    for(i=3; i*i<=N; i+=2){
        if(!is_prime[i]) continue;
        primes.push_back(i);
        for(int j=2*i; j<=N; j+=i){
            is_prime[j] = false;
        }
    }

    for(; i<=N; i+=2){
        if(is_prime[i]){
            primes.push_back(i);
        }
    }
}

int mod_pow(int n, int e, int mod){
    int ans = 1;
    n = n % mod;
    while(e != 0){
        if(e % 2 == 1){
            ans = (ans * n) % mod;
        }
        e /= 2;
        n = (n*n) % mod;
    }
    return ans;
}

int mod_inv(int n, int p){
    // n^p-2
    return mod_pow(n, p-2, p);
}

int gcd(int n, int m){
    if(n < m) return gcd(m, n);
    if(m == 0) return n;
    else return gcd(m, n%m);
}

int ll_max(int n, int m){
    if(n > m) return n;
    else return m;
}

signed main(){
    // cout << fixed << setprecision(10) << flush;
    int n;
    cin >> n;
    vector<int> a(n), A(n);
    int maxA = 0;
    for(int i=0; i<n; i++){
        cin >> a[i];
        A[i] = a[i];
        maxA = ll_max(maxA, a[i]);
    }

    vector<bool> is_prime;
    vector<int> primes;
    prime_vectors(maxA, primes, is_prime);

    int MOD = 1e9 + 7;

    int lcm = 1;
    vector<int> c(primes.size(), 0);
    for(int i=0; i<n; i++){
        for(int j=0; primes[j] * primes[j] <= a[i]; j++){
            int cj = 0;
            while(a[i] % primes[j] == 0){
                a[i] /= primes[j];
                cj++;
            }
            if(c[j] < cj){
                c[j] = cj;
            }
        }

        if(a[i] > 1){
            // a[i] 素数が残った
            int j = 0;
            for(j=0; j<primes.size(); j++){
                if(a[i] == primes[j]) break;
            }
            if(c[j] < 1){
                c[j] = 1;
            }
        }
    }

    for(int i=0; i<primes.size(); i++){
        lcm = (lcm * mod_pow(primes[i], c[i], MOD)) % MOD;
    }

    int sum = 0;
    for(int i=0; i<n; i++){
        sum = (sum + lcm * mod_inv(A[i], MOD)) % MOD;
    }
    cout << sum << endl;

    return 0;
}

Measured memory_bytes: 4888
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
  int a,b,c,d;
  cin >> a >> b >> c >> d;
  int ans=0;
  ans += min( a,b );
  ans += min( c,d );
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll countDivisible(ll a,ll b,ll m){
    if(a%m==0)
        return (b/m)-(a/m)+1;
    else
        return (b/m)-(a/m);
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    ll a,b,c,d,t1,t2,t3;
    cin>>a>>b>>c>>d;
    t1=countDivisible(a,b,c);
    t2=countDivisible(a,b,d);
    t3=countDivisible(a,b,c*d/(__gcd(c,d)));
    cout<<(b-a+1)-(t1)-(t2)+(t3)<<endl;
    return 0;
}


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

const int N=1e5+5;
const int INF=1e9;
int cost[N];
int main() {
	int K;
	scanf("%d", &K);
	deque<int> que;
	for(int i=0; i<K; i++) cost[i]=INF;
	cost[1]=0;
	que.push_back(1);
	while(que.size()) {
		int u=que.front(); que.pop_front();
		if ( cost[(u+1)%K]>cost[u]+1 ) {
			cost[(u+1)%K]=cost[u]+1;
			que.push_back((u+1)%K);
		}
		if ( cost[(u*10)%K]>cost[u] ) {
			cost[(u*10)%K]=cost[u];
			que.push_front((u*10)%K);
		}
	}
	printf("%d\n", cost[0]+1);
	return 0;
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define FOR(i, s, n) for (int i = (s); i < (n); i++)
#define rep(i, n) FOR(i, 0, n)
#define repi(i, n) FOR(i, 1, n + 1)
#define pp(v) cout << #v "=" << (v) << endl;
#define ppa(v) cout << "----\n"; rep(i,v.size()) cout << #v << "[" << i << "] = " << v[i] << endl;
#define div_ceil(a,b) ((a) + ((b) - 1)) / (b)
using namespace std;
using Graph = vector<vector<int>>;

int main() {
  vector<int> a(3);rep(i,3) cin>>a[i];
  sort(ALL(a));
  int k;cin>>k;
  rep(i,k) a[2] *= 2;
  int ans = 0;
  rep(i,3) ans += a[i];
  cout << ans << endl;
}


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

using namespace std;

#define f first
#define s second
#define pub push_back
#define pob pop_back
	
typedef vector<int> vi;
typedef vector<vi> graf;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vii> wgraf;

typedef vector<double> vd;
typedef pair<double,double> dd;
typedef vector<dd> vdd;

typedef uint64_t ui64;

int main(){

	int n;
	cin >> n;

	for(int i = 1; i <= 9; i++){

		if(n%i == 0 && n/i <= 9 && n/i >= 1){

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

		}

	}

	cout << "No" << endl;

	return 0;
}


Measured memory_bytes: 256
#include<iostream>
int main()
{
  int n;
  int u,k,v;
  int V[100][100]={0};
  std::cin>>n;
  for(int i=0;i<n;i++){
    std::cin>>u>>k;
    for(int j=0;j<k;j++){
      std::cin>>v;
      V[u-1][v-1]=1;
    }
  }
  for(int i=0;i<n;i++){
    for(int j=0;j<n-1;j++){
      std::cout<<V[i][j]<<" ";
    }
    std::cout<<V[i][n-1]<<'\n';
  }
  return 0;
}



Measured memory_bytes: 3076
#include<stdio.h>
#include<stdlib.h>
#define MAX 10000
#define MA 2000001







int main(){
  int i,j,k;
  int C[MAX+1],*A,*B;
 

  scanf("%d",&k);

  

  A = malloc(sizeof(int *) * k+1);
  B = malloc(sizeof(int *) * k+1);

   for(i = 0;i<=MAX;i++){
    C[i] = 0;
  }

  
     
  for(i = 0;i<k;i++){
    scanf("%d",&A[i+1]);
    C[A[i+1]]++;
  }

   for(i =1;i<=MAX;i++){
    C[i] = C[i] + C[i-1];
  }
  for(j = 1;j<=k;j++){
    B[C[A[j]]] = A[j];
    C[A[j]]--;
  }


  


  for(i = 1;i<=k;i++){
    if(i>1) printf(" ");
    printf("%d",B[i]);
  }
  printf("\n");
  
  

  return 0;
}



Measured memory_bytes: 17408
s = [11, 31, 41, 61, 71, 101, 131, 151, 181, 191, 211, 241, 251, 271, 281, 311, 331, 401, 421, 431, 461, 491, 521, 541, 571, 601, 631, 641, 661, 691, 701, 751, 761, 811, 821, 881, 911, 941, 971, 991, 1021, 1031, 1051, 1061, 1091, 1151, 1171, 1181, 1201, 1231, 1291, 1301, 1321, 1361, 1381]
print(" ".join(list(map(str, s[:int(input())]))))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define pb push_back
#define sz(a) int(a.size())
#define re return
using namespace std;
int main()
{
	int a,b,c;
	cin>>a>>b>>c;
	if (a==b && b==c)  cout<<"No";
	else if (a==b || b==c || a==c)  cout<<"Yes";
	else  cout<<"No";
	re 0;
}

Measured memory_bytes: 256
#include <iostream>

int five, seven, temp;

void solve() {
    five = 0;
    seven = 0;
    for (int i=0; i<3; ++i) {
        std::cin >> temp;
        if (temp == 5)
            ++five;
        else
            ++seven;
    }
    if (five == 2 && seven == 1)
        std::cout << "YES" << std::endl;
    else
        std::cout << "NO" << std::endl;
}

int main() {
    solve();
    return 0;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10 ** 9 + 10)
def input(): return sys.stdin.readline().strip()


def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    biggerA = 0
    biggerB = 0
    task = 0
    for i in range(N):
        # A[i]>B[i]なる全てのB[i]を埋めてA[i]<=B[i]とできれば勝ち
        if A[i] > B[i]:  # B[i]をcnt分埋めるというタスクがある
            task += A[i] - B[i]
        if A[i] < B[i]:  # B[i]が優っている箇所でA[i]を埋めてタスクを解消
            task -= (B[i] - A[i]) // 2

    if task <= 0:
        print('Yes')
    else:
        print('No')


resolve()

Measured memory_bytes: 4596
n, m = map(int, input().split())
a = [list(input().split()) for _ in range(m)]
s = ["0"] * n
s[0] = "1"
if m >= 2:
    for i in range(0,m-1):
        for j in range(i+1, m):
            if a[i][0] == a[j][0] and a[i][1] != a[j][1]:
                print("-1")
                exit()
for i in range(m):
    s[int(a[i][0]) - 1] = str(a[i][1])
if n != 1 and s[0] == "0":
    print("-1")
    exit()
elif m == 0 and n == 1:
    print("0")
else:
    print("".join(s))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(int i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(int i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(int i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define uniq(x) (x).erase(unique((x).begin(), (x).end()), (x).end())

struct Sushi {
    int t = -1;
    int d = -1;
};

bool operator<(const Sushi &a, const Sushi &b) {
    return a.d < b.d;
}

bool operator>(const Sushi &a, const Sushi &b) {
    return a.d > b.d;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n, k;
    cin >> n >> k;
    priority_queue<Sushi> td;
    priority_queue<Sushi, vector<Sushi>, greater<Sushi>> std;
    map<int, int> tm;
    ll answer = 0, basic = 0, bonus;
    
    rep(i, n) {
        Sushi tmp;
        cin >> tmp.t >> tmp.d;
        td.push(tmp);
    }
    
    rep(i, k) {
        Sushi s = td.top();
        basic += s.d;
        tm[s.t]++;
        std.push(s);
        td.pop();
    }
    
    bonus = (ll)sz(tm) * sz(tm);
    answer = basic + bonus;
    
    while (sz(td) > 0) {
        Sushi ts, ss;
        bool f = false;
        
        ts = td.top();
        td.pop();
        
        if (tm.count(ts.t) > 0) {
            continue;
        }
        
        while(sz(std) > 0) {
            ss = std.top();
            std.pop();
            
            if (tm[ss.t] > 1) {
                f = true;
                break;
            }
        }
        
        if (!f) {
            break;
        }
        
        tm[ss.t]--;
        tm[ts.t]++;
        bonus = (ll)sz(tm) * sz(tm);
        basic += ts.d - ss.d;
        
        answer = max(answer, basic + bonus);
    }
    
    cout << answer << endl;
    return 0;
}


Measured memory_bytes: 4724
#include <bits/stdc++.h>
typedef long long ll;
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
using namespace std;
const ll MAX_P=2999;
typedef vector<ll> vec;
ll p,inv[MAX_P];
ll mpw(ll n,ll m){
	ll r=1;
	while(m){
		if(m&1){
			r*=n;
			r%=p;
		}
		n*=n;
		n%=p;
		m>>=1;
	}
	return r;
}
ll minv(ll n){
	return mpw(n,p-2);
}
vec slv(ll n,vec &a){
	vec ret(n+1,0);
	if(n==0){
		ret[0]=a[0];
	}else{
		vec a2(n);
		REP(i,n){
			a2[i]=inv[(i-n+p)%p]*(a[i]-a[n]+p)%p;
		}
		vec f2=slv(n-1,a2);
		REP(i,n){
			ret[i+1]=f2[i];
		}
		REP(i,n){
			ret[i]-=n*f2[i]%p;
			ret[i]+=p;
			ret[i]%=p;
		}
		ret[0]+=a[n];
		ret[0]%=p;
	}
	return ret;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>p;
	vec a(p);
	REP(i,p-1){
		inv[i+1]=minv(i+1);
	}
	REP(i,p)cin>>a[i];
	vec f=slv(p-1,a);
	REP(i,p){
		if(i)cout<<' ';
		cout<<f[i];
	}
	cout<<endl;
}

Measured memory_bytes: 70912
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
void _main()
{
    int N, Z, W;
    cin >> N >> Z >> W;
    vector<int> a(N);
    rep(i, 0, N) cin >> a[i];
    if (N >= 2)
    {
        cout << max(abs(a[N - 1] - W), abs(a[N - 2] - a[N - 1])) << endl;
    }
    else
    {
        cout << abs(a[0] - W) << endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

int N, M;
int A[310][310];

int cnt[310];

int main(void) {
	cin >> N >> M;
	rep(i, N)rep(j, M) cin >> A[i][j];
	rep(i, N)rep(j, M) A[i][j]--;
	int ans = INF;

	vector<int> idx(N, 0);
	set<int> se;

	if(M == 1) {
		printf("%d\n", N); return 0;
	}
	
	rep(k, M - 1) {
		rep(i, 310) cnt[i] = 0;
		rep(i, N) cnt[A[i][idx[i]]]++;
		// rep(i, M) printf("%d ", cnt[i]);
		// printf("\n");
		// rep(i, N) printf("%d ", idx[i]);
		// printf("\n");
		int tmax = 0, idxma;
		rep(i, M) if(tmax < cnt[i]) tmax = cnt[i], idxma = i;
		// printf("ma %d idx %d\n", tmax, idxma);
		chmin(ans, tmax);
		se.insert(idxma);

		rep(i, N) while(se.count(A[i][idx[i]])) idx[i]++;
	}

	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 640
#include <stdio.h>
 
 

 
int main(void){
	int i,j,k;
	int n,num[4000];
	long long int tanka,sale_num,sale_sum[4000],sale_all[4001];
	bool judge[4001];
	
	while(scanf("%d",&n),n){
		
		//初期化

		k=0;
		for(j=0;j<=4001;j++){
			judge[j]=0;
			sale_all[j]=0;
		}
		
		for(i=0;i<n;i++){
			scanf("%d %lld %lld",&num[i],&tanka,&sale_num);
			sale_sum[i]=tanka*sale_num;
		}
		
		
		//idに対応したsaleに+
		for(i=0;i<n;i++){
			sale_all[num[i]] = sale_all[num[i]] + sale_sum[i];
		}
		
		for(i=0;i<n;i++){
			if((sale_all[num[i]] >= 1000000)&&(judge[num[i]]==0)){
				printf("%d\n",num[i]);
				judge[num[i]]=1;
				k=1;
			}
		}
		
		if(k!=1)printf("NA\n");
	}
	
	return 0;
}

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

typedef long long ll;
#define mp make_pair
#define pb push_back
#define pi pair<ll,ll>
#define ff first
#define ss second
#define MAX 100005
const ll MOD = 1000000007;

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

	int t=1;
//	cin>>t;
	while(t--){
		int n;
		cin>>n;
		
		for(int i=1;i<=9;i++)
		{
			for(int j=1;j<=9;j++)
			{
				if(i*j==n)
			    {
			    	cout<<"Yes\n";
			    	return 0;
				}
			}
		}
		cout<<"No\n";
	 
	}		
}

Measured memory_bytes: 3588
// Author : heyuhhh
// Created Time : 2020/09/19 20:25:41
#include<bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e5 + 5;
void run() {
    int n;
    cin >> n;
    vector<int> d(n + 1);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j * j <= i; j++) if (i % j == 0) {
            ++d[i];
            if (j != i / j) {
                ++d[i];
            }
        }
    }
    ll ans = 0;
    for (int i = 1; i < n; i++) {
        ans += d[i];
    }
    cout << ans << '\n';
}
int main() {
#ifdef Local
    freopen("input.in", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
    run();
    return 0;
}

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

#define TOP 1
#define BOTTOM -1

#define RIGHT 1
#define LEFT -1

#define CENTER 0

int circle_in_rectangle(int, int, int, int, int);

int main(void) {
	int W, H;
	int x, y, r;

	scanf("%d %d %d %d %d", &W, &H, &x, &y, &r);

	if (circle_in_rectangle(W, H, x, y, r)) {
		printf("Yes\n");
	} else {
		printf("No\n");
	}

	return 0;
}

int circle_in_rectangle(int W, int H, int x, int y, int r) {
	if (x < 0 || H < x) return 0;
	if (y < 0 || H < y) return 0;
	if (x - r < 0 || x + r > W || y - r < 0 || y + r > H) return 0;
	else return 1;
}


Measured memory_bytes: 2140
#include <vector>
#include <cstdio>
using namespace std;

class UnionFindTree {
public:
  UnionFindTree(int n) {
    par = vector<int>(n);
    for (int i = 0; i < n; i++) par[i] = i;
  }
  int find(int x) {
    if (x == par[x]) return x;
    else return par[x] = find(par[x]);
  }
  void unite(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx != ry) par[ry] = rx;
  }
  bool same(int x, int y) {
    return find(x) == find(y);
  }
private:
  vector<int> par;
};

int N, Q;
vector<vector<int> > G;
vector<bool> marked;
UnionFindTree tree(0);
vector<int> parent;
vector<pair<bool, int> > queries;

long long solve() {
  tree = UnionFindTree(N);
  for (int i = 0; i < N; i++) {
    if (!marked[i]) tree.unite(parent[i], i);
  }

  long long res = 0;
  for (int i = queries.size() - 1; i >= 0; i--) {
    int x = queries[i].second - 1;
    if (queries[i].first == false) {
      tree.unite(parent[x], x);
    } else {
      res += tree.find(x) + 1;
    }
  }
  return res;
}

int main() {
  while (true) {
    scanf("%d %d", &N, &Q);
    if (N == 0 && Q == 0) break;

    parent = vector<int>(N);
    G = vector<vector<int> >(N);
    for (int i = 1; i < N; i++) {
      int n; scanf("%d", &n);
      G[n-1].push_back(i);
      parent[i] = n-1;
    }

    marked = vector<bool>(N);
    marked[0] = true;
    queries = vector<pair<bool, int> >(Q);
    char buf[2];
    int qnum = 0;
    for (int i = 0; i < Q; i++) {
      int n; scanf("%s %d", buf, &n);
      if (buf[0] == 'Q') {
        queries[qnum++] = make_pair(true, n);
      } else if (!marked[n-1]) {
        marked[n-1] = true;
        queries[qnum++] = make_pair(false, n);
      }
    }
    Q = qnum;
    queries.resize(Q);
    long long ans = solve();
    printf("%lld\n", ans);
  }
}

Measured memory_bytes: 6860