akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>

using namespace std;

#define int long long
#define ar array
#define vt vector
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define sz(x) (int)(x).size()

#define F_OR(i, a, b, s) for (int i=(a); (s)>0?i<(b):i>(b); i+=(s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, 1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define EACH(x, a) for (auto& x: a)

template<class T>
bool umin(T &a, const T &b) {
    return b < a ? a = b, 1 : 0;
}

template<class T>
bool umax(T &a, const T &b) {
    return a < b ? a = b, 1 : 0;
}

template<class A>
void read(vt<A> &v);

template<class A, size_t S>
void read(ar<A, S> &a);

template<class T>
void read(T &x) {
    cin >> x;
}

void read(double &d) {
    string t;
    read(t);
    d = stod(t);
}

void read(long double &d) {
    string t;
    read(t);
    d = stold(t);
}

template<class H, class... T>
void read(H &h, T &... t) {
    read(h);
    read(t...);
}

template<class A>
void read(vt<A> &x) {
    EACH(a, x)read(a);
}

template<class A, size_t S>
void read(array<A, S> &x) {
    EACH(a, x)read(a);
}

string to_string(char c) {
    return string(1, c);
}

string to_string(bool b) {
    return b ? "true" : "false";
}

string to_string(const char *s) {
    return string(s);
}

string to_string(string s) {
    return s;
}

string to_string(vt<bool> v) {
    string res;
    FOR(sz(v))res += char('0' + v[i]);
    return res;
}

template<size_t S>
string to_string(bitset<S> b) {
    string res;
    FOR(S)res += char('0' + b[i]);
    return res;
}

template<class T>
string to_string(T v) {
    bool f = 1;
    string res;
    EACH(x, v) {
        if (!f)
            res += ' ';
        f = 0;
        res += to_string(x);
    }
    return res;
}

template<class A>
void write(A x) {
    cout << to_string(x);
}

template<class H, class... T>
void write(const H &h, const T &... t) {
    write(h);
    write(t...);
}

void print() {
    write("\n");
}

template<class H, class... T>
void print(const H &h, const T &... t) {
    write(h);
    if (sizeof...(t))
        write(' ');
    print(t...);
}

template<class T, class U>
void vti(vt<T> &v, U x, size_t n) {
    v = vt<T>(n, x);
}

template<class T, class U>
void vti(vt<T> &v, U x, size_t n, size_t m...) {
    v = vt<T>(n);
    EACH(a, v)vti(a, x, m);
}

void solve() {
    int n, m;
    read(n, m);
    
    vt<int> a(n), b(n), c(m), d(m);
    
    FOR(n) read(a[i], b[i]);
    FOR(m) read(c[i], d[i]);
    
    FOR(n) {
        int mn = 1e9;
        FOR(j, m) {
            mn = min(mn, abs(c[j] - a[i]) + abs(d[j] - b[i]));
        }
        
        FOR(j, m) {
            if (abs(c[j] - a[i]) + abs(d[j] - b[i]) == mn) {
                print(j + 1);
                break;
            }
        }
    }
}

int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int tt = 1;
//    read(tt);
    FOR(tt) {
//        write("Case #", i + 1, ": ");
        solve();
    }
    
}



Measured memory_bytes: 3692
import sys
input = sys.stdin.readline

#Z[i]:length of the longest list starting from S[i] which is also a prefix of S
def Z_algorithm(s):
    N = len(s)
    Z_alg = [0]*N

    Z_alg[0] = N
    i = 1
    j = 0
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        Z_alg[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k + Z_alg[k]<j:
            Z_alg[i+k] = Z_alg[k]
            k += 1
        i += k
        j -= k
    return Z_alg


n = int(input())
a = tuple(map(int,input().split()))
b = tuple(map(int,input().split()))


BAA = []
for i in range(n-1):
    BAA.append(b[i]^b[i+1])
BAA.append(b[0]^b[-1])

BAA.append(-1)

for i in range(n-1):
    BAA.append(a[i]^a[i+1])
BAA.append(a[0]^a[-1])
for i in range(n-1):
    BAA.append(a[i]^a[i+1])
BAA.append(a[0]^a[-1])

z = Z_algorithm(BAA)

for k in range(n):
    if z[n+k+1] >= n:
        print(k,b[0]^a[k])

Measured memory_bytes: 121680
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; }

int main() {
	int N; int x;
	while(~scanf("%d%d", &N, &x)) {
		vector<int> a(N);
		for(int i = 0; i < N; ++ i)
			scanf("%d", &a[i]);
		ll ans = 0;
		rep(i, N) {
			int t = max(0, (i == 0 ? 0 : a[i - 1]) + a[i] - x);
			a[i] -= t;
			ans += t;
		}
		printf("%lld\n", ans);
	}
	return 0;
}


Measured memory_bytes: 768
#include <iostream>
#include <iomanip>
using namespace std;
int main(void){
    int n;
    double d[3002][3002],q=0;
    cin>>n;
    d[0][0]=1;
    for(int i=1;i<=n;i++){
        double p;
        cin>>p;
        d[i][0]=d[i-1][0]*(1-p);
        for(int j=1;j<=i-1;j++){
            d[i][j]=d[i-1][j]*(1-p)+d[i-1][j-1]*p;
        }
        d[i][i]=d[i-1][i-1]*p;
    }
    for(int i=n;i*2>n;i--){
        q+=d[n][i];
    }
    cout<<setprecision(12)<<q<<endl;
}



Measured memory_bytes: 70016
A, B,H,M = map(int, input().split())

#B分針の位置
M_kakudo = 6 * M
#A時間針の位置
if(H>=12):
  H = H-12
H_kakudo = 30 * H
H_kakudo = M*1/2 + H_kakudo


#針の間の角度
kakudo = abs(H_kakudo-M_kakudo)


import math

a_2 = 0
a_2 = A*A + B*B - 2*B*A*math.cos(math.radians(kakudo))
import numpy
print(numpy.sqrt(a_2))

#print(H_kakudo,M_kakudo)
#print(kakudo)

Measured memory_bytes: 27180
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define MOD 1000000007
#define pb push_back
#define mp make_pair

void solve()
{
	int n, m;
	cin >> n >> m;
	char arr[n][m];
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> arr[i][j];
	int dp[n][m];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (arr[i][j] == '#')
				dp[i][j] = -1;
			else
				dp[i][j] = 0;
		}
	}
	for (int i = 0; i < n; i++)
	{
		if (dp[i][0] == -1)
			break;
		else
			dp[i][0] = 1;
	}
	for (int j = 0; j < m; j++)
	{
		if (dp[0][j] == -1)
			break;
		else
			dp[0][j] = 1;
	}
	for (int i = 1; i < n; i++) {
		for (int j = 1; j < m; j++) {
			if (dp[i][j] == -1)
				continue;
			if (dp[i - 1][j] == -1 && dp[i][j - 1] == -1)
				continue;
			else if (dp[i - 1][j] == -1)
			{
				dp[i][j] = dp[i][j - 1];
			}
			else if (dp[i][j - 1] == -1)
			{
				dp[i][j] = dp[i - 1][j];
			}
			else
			{
				dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % MOD;
			}
		}
	}
	// for (int i = 0; i < n; i++) {
	// 	for (int j = 0; j < m; j++) {
	// 		cout << dp[i][j] << " ";
	// 	}
	// 	cout << endl;
	// }

	cout << dp[n - 1][m - 1] << "\n";
}

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

Measured memory_bytes: 8396
#include<bits/stdc++.h>
using namespace std;
string s;
int main()
{
    cin>>s;
    int len=s.length();
    for(int i=0;i<len;i++)
    {
        if(s[i]=='C')
        {
            for(int j=i + 1;j<len;j++)
            {
                if(s[j]=='F')
                {
                    cout<<"Yes"<<endl; 
                    return 0;
                }
            }
        }
    }
    cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 384
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringJoiner;
import java.util.StringTokenizer;
import java.util.function.IntUnaryOperator;
import java.util.function.LongUnaryOperator;

class Main {
    static In in = new In();
    static Out out = new Out();
    static long mod = 1000000007;
    static long inf = 0xfffffffffffffffL;

    void solve() {
        String s = in.next();
        out.println(s.replaceAll(".", "x"));
    }

    public static void main(String[]$) {
        new Main().solve();
        out.flush();
    }
}

class In {
    private BufferedReader reader = new BufferedReader(new InputStreamReader(System.in), 0x10000);
    private StringTokenizer tokenizer;

    String next() {
        try {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(reader.readLine());
            }
        } catch (IOException ignored) {
        }
        return tokenizer.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    char[][] nextCharArray(int n, int m) {
        char[][] a = new char[n][m];
        for (int i = 0; i < n; i++) {
            a[i] = next().toCharArray();
        }
        return a;
    }

    int[] nextIntArray(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = nextInt();
        }
        return a;
    }

    int[] nextIntArray(int n, IntUnaryOperator op) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = op.applyAsInt(nextInt());
        }
        return a;
    }

    long[] nextLongArray(int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = nextLong();
        }
        return a;
    }

    long[] nextLongArray(int n, LongUnaryOperator op) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = op.applyAsLong(nextLong());
        }
        return a;
    }
}

class Out {
    private static PrintWriter out = new PrintWriter(System.out);

    void println(Object... a) {
        StringJoiner joiner = new StringJoiner(" ");
        for (Object obj : a) {
            joiner.add(String.valueOf(obj));
        }
        out.println(joiner);
    }

    void flush() {
        out.flush();
    }
}


Measured memory_bytes: 25300
#include <iostream>
#include <map>
#include <utility>
using namespace std;
typedef pair<int, int> P;

class UnionFind
{
    int par[200002], rank[200002];
    
public:
    UnionFind(int n){
        for(int i = 0; i < n; i++){
            par[i] = i;
            rank[i] = 0;
        }
    }
    
    int find(int i){
        if(i == par[i]) return i;
        return par[i] = find(par[i]);
    }
    
    bool same(int i, int j){
        return par[i] == par[j];
    }
    
    void unite(int i, int j){
        if(same(i, j)) return;
        i = find(i), j = find(j);
        if(rank[i] < rank[j]) par[i] = j;
        else{
            par[j] = i;
            if(rank[i] == rank[j]) rank[i]++;
        }
    }
};

int main()
{
    int n, k, l;
    cin >> n >> k >> l;
    int p[100002], q[100002], r[100001], s[100002];
    UnionFind u(n), t(n);
    for(int i = 0; i < k; i++){
        cin >> p[i] >> q[i];
        p[i]--;
        q[i]--;
        u.unite(p[i], q[i]);
    }
    for(int i = 0; i < l; i++){
        cin >> r[i] >> s[i];
        r[i]--;
        s[i]--;
        t.unite(r[i], s[i]);
    }
    map<P, int> mp;
    for(int i = 0; i < n; i++){
        mp[P(u.find(i), t.find(i))]++;
    }
    for(int i = 0; i < n; i++){
        cout << mp[P(u.find(i), t.find(i))] << endl;
    }
}


Measured memory_bytes: 17664
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <numeric>
#include <set>
#include <cstdlib>
#include <queue>
#include <map>

using namespace std;

typedef long long llint;
typedef long double ld;
#define inf 1e18
#define mod 1000000007
priority_queue<llint,vector<llint>,greater<llint>> que;
//priority_queue<llint> q;

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

string s;


void solve(){
  cin >> s;
  if(s.size()==2){
    if(s[0]==s[1]){
      cout << 1 << " " << 2 << endl;
      return;
    }
  }

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

  cout << -1 << " " << -1 << endl;
}

int main(int argc, char *argv[]) {
  solve();
  return 0;
}


Measured memory_bytes: 512
//1405
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cassert>
#include<sstream>
#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<utility>
#include<numeric>
#include<algorithm>
#include<bitset>
#include<complex>

using namespace std;

typedef unsigned uint;
typedef long long Int;
typedef vector<int> vint;
typedef pair<int,int> pint;

int main(){
	int n;
	while(cin >> n){
		vector<pint> a;
		if(n==0) break;
		int m;
		cin >> m;
		pint tmp;
		cin >> tmp.first >> tmp.second;
		a.push_back(pint(0,0));
		for(int i=1;i<m;i++){
			pint in;
			cin >> in.first >> in.second;
			a.push_back(pint(in.first-tmp.first,in.second-tmp.second));
		}
		
		for(int ii=0;ii<n;ii++){
			cin >> m;
			cin >> tmp.first >> tmp.second;
			vector<pint> b;
			b.push_back(pint(0,0));
			for(int i=1;i<m;i++){
				pint in;
				cin >> in.first >> in.second;
//				cout << in.first <<" "<< in.second << endl;
				b.push_back(pint(in.first-tmp.first,in.second-tmp.second));
			}
			if(a.size()==b.size()){
				int f=0;
				for(int k=0;k<4;k++){
					f=0;
					for(int j=0;j<a.size();j++){
//						cout << a[j].first << " " << a[j].second << "   " << b[j].first << " " << b[j].second<< endl;
						if(a[j]!=b[j]) f=1;
					}
					if(f==0){
						cout << ii+1 << endl;
						break;
					}
					for(int j=0;j<b.size();j++){
						swap(b[j].first,b[j].second);
						b[j].first*=-1;
					}
				}
				if(f==1){
					f=0;
					reverse(b.begin(),b.end());
					tmp = b[0];
					for(int j=0;j<b.size();j++){
						b[j].first-=tmp.first;
						b[j].second-=tmp.second;
					}
					for(int k=0;k<4;k++){
						f=0;
						for(int j=0;j<a.size();j++){
							//						cout << a[j].first << " " << a[j].second << "   " << b[j].first << " " << b[j].second<< endl;
							if(a[j]!=b[j]) f=1;
						}
						if(f==0){
							cout << ii+1 << endl;
							break;
						}
						for(int j=0;j<b.size();j++){
							swap(b[j].first,b[j].second);
							b[j].first*=-1;
						}
					}
				}
			}
		}
		cout << "+++++" << endl;
	}
				
			
	
	return 0;
}
	

Measured memory_bytes: 0
# coding: utf-8

# https://atcoder.jp/contests/abc084/tasks/abc084_c
# 18:09-18:34 done


def main():
    N = int(input())
    C, S, F = [None] * (N-1), [None] * (N-1), [None] * (N-1)
    for i in range(N-1):
        C[i], S[i], F[i] = map(int, input().split())
    
    ans = [None] * N
    for i in range(N-1):
        tim = 0
        for j in range(i, N-1):
            if tim <= S[j]:
                tim = S[j]
            else:
                if (tim-S[j]) % F[j] > 0:
                    tim = S[j] + ((tim-S[j]) // F[j] + 1) * F[j]
            tim += C[j]
        
        ans[i] = tim
    
    ans[-1] = 0

    for a in ans:
        print(a)


main()
# print(main())


Measured memory_bytes: 3188
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main(void){
    // Your code here!
    long long a,b;
    cin>>a>>b;
    long long ans=1<<30;
    if(b-a>0)ans=min(ans,b-a);
    if(2-b+a>0)ans=min(ans,2-b+a);
    if(1+a+b>0)ans=min(ans,1+a+b);
    if(1-a-b>0)ans=min(ans,1-a-b);
    cout<<ans<<endl;
    //cout<<min({b-a,2-b+a,1+a+b,1-a-b)})<<endl;
}


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

int main(){
  // 入力
  int N;
  cin >> N;
  
  vector<char> vec(N);
  for(int i = 0; i < N; i++){
    cin >> vec.at(i);
  }
  
  //
  for(int i = 0; i < N; i++){
    if(vec.at(i) == 'Y'){
      cout << "Four" << endl;
      break;
    }
    if(i == N-1){
      cout << "Three" << endl;
      break;
    }
  }
}

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

struct Point{int x,y;};

int main(){
  int n,m,l,x,y,i,j,k,a;
  char d;
  int flag;
  
  cin >> n;
  while(n!=0){
    Point p[21];
    int v[21] = {};
    Point now;
    now.x=10;
    now.y=10;
    flag=0;
    for(i=0;i<n;i++) {
      cin >> x >> y;
      p[i].x=x;
      p[i].y=y;
    }
    k=0;
    cin >> m;
    for(i=0;i<m;i++){
      cin >> d >> l;
      for(a=0;a<l;a++){
      if(d=='N') now.y++;
      if(d=='E') now.x++;
      if(d=='S') now.y--;
      if(d=='W') now.x--;
      for(j=0;j<n;j++){
	if(now.x==p[j].x&&now.y==p[j].y&&v[j]==0){
	  k++;
	  v[j]=1;
	}
      }
      }
    }
    if(k==n) cout << "Yes" << endl;
    else cout << "No" << endl;
    cin >> n;
  }
  return 0;
}

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

using namespace std;

typedef long long ll;

const int N = 2e5 + 5;

int n;

struct Edge{

    int v, next;

    ll w;

}e[N << 1];

int head[N], tot;

int ans[N] ;

void adde(int u, int v, ll w) {

    e[tot].v = v; e[tot].w = w; e[tot].next = head[u]; head[u] = tot++;

}

void dfs(int u, int fa, ll d) {

    for(int i = head[u]; i != -1; i = e[i].next) {

        int v = e[i].v;

        if(v == fa) continue ;

 

        if((d + e[i].w) & 1) ans[v] = 1;

        dfs(v, u, d + e[i].w) ;

    }

}

int main() {

    ios::sync_with_stdio(false); cin.tie(0);

    cin >> n;

    memset(head, -1, sizeof(head)) ;

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

        int u, v; ll w;

        cin >> u >> v >> w;

        adde(u, v, w); adde(v, u, w) ;

    }

    dfs(1, 0, 0) ;

    for(int i = 1; i <= n; i++) cout << ans[i] << '\n';

    return 0;

}



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

int main(){
    int N; 
    cin >> N;
    vector<long long> A(N);
    for(int i = 0; i < N; i++)cin >> A[i];
    int four = 0;
    int two = 0;
    int odd = 0;
    for(int i = 0; i < N; i++){
        if(A[i] % 4 == 0){
            four++;
        }else if(A[i] % 2 == 0){
            two++;
        }else{
            odd++;
        }
    }
    
    if(two > 0)odd++;
    
    if(odd - four < 2)cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,x,n) for(int i=x; i<(n); i++)
#define all(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const long long INF = numeric_limits<long long>::max();
long long w[1100],v[1100];
long long dp[110][110000];// dp[i][j] := i番目までの品物を、価値の総和がｊとなるように取った時の品物の重さの総和
int main()
{
    int N;
    long long W;
    cin >> N >> W;
    rep(i,N){
        cin >> w[i] >> v[i];

    }
    rep(i,110){
        rep(j,100100){
        dp[i][j] = 10000000000;
        }
    }
    dp[0][0] = 0;
    rep(i,N){
        rep(j,110000){
            if (j- v[i] <0){
                dp[i+1][j] = min(dp[i+1][j],dp[i][j]);
            }
            else{
                dp[i+1][j] = min(dp[i][j], dp[i][j-v[i]]+w[i]);
            }
            
        }
    }
    long long res = 0;
    rep(i,100100){
        if (dp[N][i] <= W){
            res = i;
        }
    }

    
   cout << res << endl;

    
    return 0;
}

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

int main() {
  int n,ans = 0,yuuyo = 0;
  cin >> n;
  vector<int> a(n);
  for(int k = 0; k < n; k++){
    cin >> a.at(k);
  }
  sort(a.begin(), a.end());
  for(int i = a.at(1); i > 0; i--){
    yuuyo = 1;
    for(int j = 0; j < n; j++){
      if(a.at(j) % i != 0)
        yuuyo--;
    }
    if(yuuyo >= 0){
      ans = i;
      break;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while(cin>>n,n){
        int mas[15][15]={},x=n/2,y=x+1;
        mas[y][x]=1;
        for(int i=2;i<=n*n;i++){
            x+=1;y+=1;
            while(1){
                if(y==n)y=0;
                else if(x==n)x=0;
                else if(x<0)x=n-1;
                else if(mas[y][x]!=0){
                    y+=1;x-=1;
                }
                else {
                    mas[y][x]=i;
                    break;
                }
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++)cout<<setw(4)<<mas[i][j];
            cout<<endl;
        }
    }
}

Measured memory_bytes: 1172
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
 
const ll INF = 1ll<<60;
 
typedef pair<ll,ll> P;
 
int main() {
  ll n, x, d;
  cin >> n >> x >> d;
 
  if (d == 0) {
    if (x == 0) {
      cout << 1 << endl;
    } else {
      cout << n+1 << endl;
    }
    return 0;
  }
 
  map<int,vector<P>> mp;
  rep(i,n+1) {
    ll s = x*i;
    ll l = (ll)i*(i-1)/2;
    ll r = l + (ll)i*(n-i);
    s += l*d;
    r -= l;
    mp[(s%d + d)%d].emplace_back(s,r);
  }
 
  ll ans = 0;
  for (auto p : mp) {
    auto a = p.second;
    int m = a.size();
    rep(i,m) a[i].first = (a[i].first-p.first)/d;
    vector<P> ev;
    rep(i,m) {
      ev.emplace_back(a[i].first, 1);
      ev.emplace_back(a[i].first+a[i].second+1, -1);
    }
    sort(ev.begin(), ev.end());
    ll cnt = 0, pre = -INF;
    for (auto e : ev) {
      ll len = e.first-pre;
      if (cnt) ans += len;
      cnt += e.second;
      pre = e.first;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 25464
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a; i < b; ++i)
const long long INF = 1e18;

struct Edge { int to; long long cost; };

template<class T>
vector<T> Dijkstra(const vector<vector<Edge>> &G, int s, T def) {
    using P = pair<T, int>;
    priority_queue<P, vector<P>, greater<P>> pq;
    vector<T> dist((int)G.size(), def);
    pq.push({0, s});
    dist[s] = 0;
    while(!pq.empty()) {
        int cur = pq.top().second; pq.pop();
        for(auto &e : G[cur]) {
            if(dist[e.to] > dist[cur] + e.cost) {
                dist[e.to] = dist[cur] + e.cost;
                pq.push({dist[e.to], e.to});
            }
        }
    }
    return dist;
}

long long Diameter(const vector<vector<Edge>> &G) {
    auto dist = Dijkstra(G, 0, INF);
    int t = max_element(dist.begin(), dist.end()) - dist.begin();
    auto dist2 = Dijkstra(G, t, INF);
    return *max_element(dist2.begin(), dist2.end());
}

void solve() {
    int N; cin >> N;
    vector<vector<Edge>> G(N);
    for(int i = 0; i < N - 1; ++i) {
        int a, b;
        long long c;
        cin >> a >> b >> c;
        G[a].push_back({b, c});
        G[b].push_back({a, c});
    }
    cout << Diameter(G) << '\n';
}

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



Measured memory_bytes: 12508
"""
a=[0]*(n)
for i in range(n):
    if(i<2):
        a[i]=1
    else:
        a[i]=i*a[i-2]
for i in range(n):
    print(i,a[i]))
"""

def cal(n):
    res=0
    while(n>0):
        res+=n//5
        n//=5
    return res

n=int(input())
if(n==0):
    print(0)
elif(n%2==1):
    print(0)
else:
    print(cal(int(n//2)))


Measured memory_bytes: 3060
#include <iostream>
#include <math.h>
#include <map>
using namespace std;
int main()
{
  long N, P;
  cin >> N >> P;
  map<long, long> mp;
  for (long i = 2; i * i <= P; i++)
  {
    while (P % i == 0)
    {
      if (mp.find(i) == mp.end())
        mp[i] = 1;
      else
        mp[i] = mp[i] + 1;
      P /= i;
    }
  }
  if (P != 1)
  {
    if (mp.find(P) == mp.end())
      mp[P] = 1;
    else
      mp[P] = mp[P] + 1;
  }
  long ans = 1;
  for (auto m : mp)
  {
    ans *= pow(m.first, m.second / N);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
from collections import deque

H, W = map(int, input().split())
S = [input() for _ in range(H)]
visited = [[False] * W for _ in range(H)]
ans = 0
for si in range(H):
    for sj in range(W):
        if visited[si][sj]:
            continue
        visited[si][sj] = True
        queue = deque()
        queue.append((si, sj))
        black = 0
        white = 0
        while queue:
            i, j = queue.popleft()
            if S[i][j] == '#':
                black += 1
            else:
                white += 1
            for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                ni, nj = i+di, j+dj
                if 0 <= ni < H and 0 <= nj < W and not visited[ni][nj] and S[i][j] != S[ni][nj]:
                    visited[ni][nj] = True
                    queue.append((ni, nj))
        ans += black * white
print(ans)

Measured memory_bytes: 47836
import java.util.*;

public class Main {

public static void main(String[] args) {

      Scanner scan = new Scanner(System.in);
      String s = scan.nextLine();

      boolean valid = true;

      for (int i = 0; i < s.length() && valid; i++){
        for (int j = i+1; j < s.length() && valid; j++){
          if (s.charAt(i) == s.charAt(j)){
              valid = false;
          }
        }
      }

      if (valid){
        System.out.println("yes");
      }
      else {
        System.out.println("no");
      }
}

}


Measured memory_bytes: 23508
use strict;
use warnings;
use utf8;
use v5.18;

use List::Util qw(max);

my $s = <STDIN>;
my $K = <STDIN>;

my @ret = ();
for my $i ( 0 .. length $s ) {
    for my $j ( 1 .. $K ) {
        push @ret => substr( $s, $i, $j ) if $i + $j < length $s;
    }
}

my %hash = map { $_, 1 } @ret;
my @unique = keys %hash;
@ret = sort @unique;

# print "@ret\n";
print "$ret[$K - 1]\n";


Measured memory_bytes: 7936
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, a, b) for(int i = a; i < b; i++)
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  FastIO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef long long int lli;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }

int dx[] = {1, 1, 0, -1, -1, -1, 0, 1};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};

int C[1000005];

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    sort(all(a));
    for (int x: a){
        if (C[x] != 0){
            C[x] = 2;
            continue;
        }
        for(int i = x; i < 1000005; i += x) C[i]++;
    }
    int ans = 0;
    for (int x: a){
        if (C[x] == 1) ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 7916
#include <algorithm>
#include <iostream>

using namespace std;

int main() {
  int basePay = 1000;
  int change, N;

  cin >> N;
  if (N % basePay == 0) {
    change = 0;
  } else {
    change = (basePay - (N % basePay));
  }

  cout << change << endl;
}


Measured memory_bytes: 3148
#include <cstdio>

int N,Q;
const int MAXN=5e5+10;

char S[MAXN];
int BIT[MAXN][26];

int len(int i){
    return i&(-i);
}

void build(){
    for(int i=1;i<=N;i++){
        for(int k=0;k<26;k++) BIT[i][k]=BIT[i-1][k];
        BIT[i][S[i]-'a']++;
    }

    for(int i=N;i>=1;i--){
        int pre=i-len(i);
        for(int k=0;k<26;k++) BIT[i][k]-=BIT[pre][k];
    }
}

void update(int i,char cfrom,char cto){
    if (cfrom==cto) return;
    if (i>N) return;
    // printf("i=%d c=%c\n",i,cto);

    BIT[i][cfrom-'a']--;
    BIT[i][cto-'a']++;
    update(i+len(i),cfrom,cto);
}

int query(int l,char c){
   if (l<1) return 0;
   return BIT[l][c-'a']+query(l-len(l),c);
}

int main(){
    scanf("%d",&N);
    scanf("%s",S+1);
    build();

    scanf("%d",&Q);
    for(int k=0;k<Q;k++){
        int t;
        scanf("%d",&t);
        if (t==1){
            int i;
            char c;
            scanf("%d %c",&i,&c);
            update(i,S[i],c);
            S[i]=c;
        }else{
            int l,r;
            scanf("%d%d",&l,&r);
            int kind=0;
            for(char c='a';c<='z';c++) if (query(r,c)-query(l-1,c)) kind++;
            printf("%d\n",kind);
        }
    }

    return 0;
}

Measured memory_bytes: 51456
#include<bits/stdc++.h>
#define fi first
#define se second
#define lson l,mid,p<<1
#define rson mid+1,r,p<<1|1
#define pb push_back
#define ll long long
using namespace std;
const int inf=1e9;
const int mod=1e9+7;
const int maxn=1e5+10;
int a[maxn],b[maxn],x[maxn],y[maxn],c[maxn],vis[maxn],n;

int main(){
	//ios::sync_with_stdio(false);
	//freopen("in","r",stdin);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		x[i]=i;
	}
	for(int i=1;i<=n;i++){
		cin>>b[i];
		y[i]=i;
	}
	sort(x+1,x+n+1,[](int i,int j){return a[i]<a[j];});
	sort(y+1,y+n+1,[](int i,int j){return b[i]<b[j];});
	for(int i=1;i<=n;i++){
		if(a[x[i]]>b[y[i]]){
			cout<<"No"<<endl;
			return 0;
		}
	}
	int j=1;
	for(int i=1;i<=n;i++){
		while(a[x[j]]<=b[y[i]]&&j<=n) j++;
		if(j-1>i){
			cout<<"Yes"<<endl;
			return 0;
		}
	}
	for(int i=1;i<=n;i++) c[x[i]]=y[i];
	int ans=0;
	for(int i=1;i<=n;i++) if(!vis[x[i]]){
		int st=x[i],cnt=0;
		while(!vis[st]){
            vis[st]=1;
			st=c[st];
			cnt++;
		}
		ans+=cnt-1;
	}
	if(ans<=n-2) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//namespace mp = boost::multiprecision;

using namespace std;

const double PI = 3.14159265358979323846;
typedef long long ll;
const long double EPS = 1e-9;

#define rep(i, n) for (int i = 0; i < (n); ++i)
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
typedef pair<ll, ll> P;
const ll INF = 10e17;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define ret() return 0;

double equal(double a, double b) {
    return fabs(a - b) < DBL_EPSILON;
}

std::istream &operator>>(std::istream &in, set<char> &o) {
    string a;
    in >> a;
    for (char c : a) o.insert(c);
    return in;
}

std::istream &operator>>(std::istream &in, queue<int> &o) {
    ll a;
    in >> a;
    o.push(a);
    return in;
}

bool contain(set<char> &s, char a) { return s.find(a) != s.end(); }

//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);

typedef priority_queue<P, vector<P>, greater<P> > PQ_ASK;


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

    unsigned long long ans = a * b;
    cout << ans << endl;

}


Measured memory_bytes: 3764
import collections
from math import gcd
import sys
input=sys.stdin.readline
def main():
    n=int(input())
    c=collections.Counter()
    mod=10**9+7
    for _ in range(n):
        a,b=map(int,input().split())
        g=abs(gcd(a,b))
        if g==0:
            g=1
        a//=g
        b//=g
        c[(a,b)]+=1
    ans=1
    s=set()
    for i,j in c:
        if (i,j)==(0,0):
            continue
        if (i,j) not in s:
            s.add((i,j))
            s.add((-i,-j))
            s.add((-j,i))
            s.add((j,-i))
            ans*=(pow(2,c[(i,j)]+c[(-i,-j)],mod)+pow(2,c[(j,-i)]+c[(-j,i)],mod)-1)%mod
    print((ans-1+c[(0,0)])%mod)

if __name__ == "__main__":
    main()


Measured memory_bytes: 160628
#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 1000000000000



int main(){
	
	long long N;
	cin>>N;
	
	for(int i=1;i<=3500;i++){
		for(int j=1;j<=3500;j++){
			
			long long a = N*i*j;
			long long b = 4*i*j-N*i-N*j;
			
			if(b<=0)continue;
			if(a%b!=0)continue;
			
			long long k = a/b;
			if(k<=0||k>3500)continue;
			
			cout<<i<<' '<<j<<' '<<k<<endl;
			return 0;
		}
	}
			
	
	
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <algorithm>
#include <set>
#define MOD1 1000000007
#define MOD2 998244353
#define LIMIT1 200002
#define LIMIT2 500002
typedef long long ll;
typedef long double ld;
typedef const void cv;
#define rep(i,n) for((i)=0;(i)<(n);(i)++)
#define per(i,n) for((i)=(n)-1;(i)>=0;(i)--)
#define max(a,b) ((a)>(b) ? (a) : (b))
#define min(a,b) ((a)<(b) ? (a) : (b))
#define zt(a,b) (max((a),(b))-min((a),(b)))
#define absl(v) labs((v))
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll nPr(int n,int r){ll i,result=1;rep(i,r){result*=(ll)(n-i);}return result;}
ll nCr(int n,int r){ll i,result=1;if(n<r) return 0;rep(i,min(r,n-r)){result*=(ll)(n-i);result/=(ll)(i+1);}return result;}
#define nHr(n,r) nCr((int)((n)+(r)+1),(int)(r))
#define sankaku(x) (((x)*((x)+1))/2)
int dx[8]={1,0,-1,0,1,-1,-1,1},dy[8]={0,1,0,-1,1,1,-1,-1};
int upint(cv *a, cv *b) { return *(int *)a < *(int *)b ? -1 : *(int *)a > *(int *)b ? 1 : 0; }
int downint(cv *a, cv *b) { return *(int *)a < *(int *)b ? 1 : *(int *)a > *(int *)b ? -1 : 0; }
int upchar(cv *left, cv *right) {return strcmp((char *)left,(char *)right);}
int downchar(cv *left, cv *right) {return strcmp((char *)right,(char *)left);}
void tmpInit(int *c,ll m) {ll i;rep(i,m) c[i]=i;}
ll modpow(ll a, ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1){
            res *= a; if(mod>=1) res %= mod;
        }
        a *= a; if(mod>=1) a %= mod;
        n >>= 1;
    }
    return res;
}
void initialize(){
    
}
//int visited[LIMIT1]={0};
int dist[LIMIT1]={0};
std::vector<int> tree[LIMIT1];
std::vector<int> cc[2];
ll sizeA=0,sizeB=0;
void dfs(int p,int count){
  dist[p]=count;
  cc[count%2].push_back(p);
  if(count%2==0) sizeA++;
  else sizeB++;
  for(int q : tree[p]){
    if(dist[q]==-1) dfs(q,count+1);
  }
}
int main(void){
  initialize();
  ll n,m,i,j,k;
  int a,b,result[LIMIT1];
  std::set<int> enable;
  char s[LIMIT1];
  
  scanf("%lld",&n);
  rep(i,n-1){
    scanf("%d %d",&a,&b);
    a--;b--;
    tree[a].push_back(b);
    tree[b].push_back(a);
  }
  rep(i,n){
    enable.insert(i+1);
    dist[i]=-1;
  }
  dfs(0,0);
  if(sizeA>=(ld)n/3 && sizeB>=(ld)n/3){
    m=2;
    k=1;
    for(int l : cc[0]){
      result[l]=m;
      //enable.erase(m);
      //printf("%lld ",m);
      m+=3;
      if(m>n) m=3;
    }
    for(int l : cc[1]){
      result[l]=k;
      //enable.erase(k);
      k+=3;
      if(k>n) k=m;
    }
  }else if(sizeA<(ld)n/3){
    m=3;
    for(int l : cc[0]){
      result[l]=m;
      m+=3;
    }
    k=1;
    for(int l : cc[1]){
      if(k%3==0&&k<m) k++;
      result[l]=k;
      k++;
    }
  }else{
    m=3;
    for(int l : cc[1]){
      result[l]=m;
      m+=3;
    }
    k=1;
    for(int l : cc[0]){
      if(k%3==0&&k<m) k++;
      result[l]=k;
      k++;
    }
  }
  rep(i,n) printf("%d ",result[i]);
  //enable.clear();
  return 0;
}

Measured memory_bytes: 26996
n, m = map(int, input().split())
xlist = list(sorted(map(int, input().split())))
dxlist = sorted([nx - px for px, nx in zip(xlist, xlist[1:])], key=lambda x: -x)
if n >= m:
  print(0)
else:
  print(xlist[-1] - xlist[0] - sum(dxlist[:n-1]))

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

n2=int(n**(0.5)+0.5)+1+1
f=[0]*(n+1)

for x in range(1,n2):
    for y in range(1,n2):
        for z in range(1,n2):
            v=x*x+y*y+z*z+x*y+y*z+z*x
            if v<=n:
                f[v]+=1
                
for v in range(1,n+1):
    print(f[v])
    

Measured memory_bytes: 9564
#![allow(unused_parens)]
#![allow(unused_imports)]
#![allow(non_upper_case_globals)]


macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [$t:tt]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}


#[cfg(debug_assertions)]
macro_rules! mydbg {
    //($arg:expr) => (dbg!($arg))
    ($arg:expr) => (println!("{:?}",$arg));
}


#[cfg(not(debug_assertions))]
macro_rules! mydbg {
    ($($arg:expr),*) => {};
}


use std::cmp;
use std::collections::HashMap;





fn main() {

    input! { 
       n: usize,
       h: i64,
       sord : [(i64,i64);n],
    }

    let mut ans = 0;

    let mut sord0 = vec![(0,0,0);n];
    let mut sord1 = vec![(0,0);n];
    let mut sord2 = vec![(0,0);n];

    let mut sord = sord;

    for i in 0..n{
        sord0[i] = (i,sord[i].0, sord[i].1);
    }

    sord0.sort_by(|a,b|{
        if(a.1 < b.1) {cmp::Ordering::Greater}
        else if(a.1==b.1){cmp::Ordering::Equal}
        else{cmp::Ordering::Less}
    });

    for i in 0..n{
        sord1[i] = (sord0[i].0,sord0[i].1);
    }

    sord0.sort_by(|a,b|{
        if(a.2 < b.2) {cmp::Ordering::Greater}
        else if(a.2==b.2){cmp::Ordering::Equal}
        else{cmp::Ordering::Less}
    });

    
    for i in 0..n{
        sord2[i] = (sord0[i].0,sord0[i].2);
    }

   
   mydbg!(sord1);
   mydbg!(sord2);
   let mut h = h;
   
   let damage = sord1[0];
   for i in 0..n{
       let s = sord2[i];
        if(s.1 > damage.1){
           h -= s.1;
           ans+=1;
       }
       else{
           break;
       }

       if(h<=0){
           break;
       }
   }

   if(h>0){
        let tmp = h / damage.1;
        ans += tmp-1;
        h -= (tmp-1) * damage.1;
       while(true){
           h-=damage.1;
           
           ans+=1;
           if(h<=0){
               break;
           }
       }
   }


   
   
    
    
    println!("{}",ans);


}


Measured memory_bytes: 19704
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;

namespace aizu1
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int[] A = Array.ConvertAll(Console.ReadLine().Split(' '), new Converter<string, int>(s => int.Parse(s)));

            int x = Partition(A, 0, n - 1);

            string[] res = Array.ConvertAll(A, new Converter<int, string>((a) => a.ToString()));

            res[x] = "[" + res[x] + "]";

            Console.WriteLine(string.Join(" ",res));

        }

        static int Partition(int [] A, int p, int r)
        {
            int x = A[r];
            int i = p - 1;
            for(int j=p;j<r;j++)
            {
                if(A[j]<=x)
                {
                    i++;
                    if (i != j)
                    {
                        int t = A[i];
                        A[i] = A[j];
                        A[j] = t;
                    }
                }

            }
            int tmp = A[i + 1];
            A[i + 1] = A[r];
            A[r] = tmp;

            return i+1;
        }
    }
}

Measured memory_bytes: 17180
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N , ans=0;
  bool ok=true;
  cin>>N;
  vector<int> a(N);
  for(int i=0;i<N;i++){
    cin>>a[i];
  }
  while(ok){
  for(int i=0;i<N;i++){
    if(a[i]%2!=0){
      cout<<ans<<endl;
      ok=false;
      break;
  }
  }
  ans++;
    for(int i=0;i<N;i++){
      a[i]=a[i]/2;
    }
  }
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
	int X, Y;
	cin >> X >> Y;

	//a+b=X;
	//2a+4b=Y;

	for (int a = 0; a <= X; a++) {
		if (2 * a + 4 * (X - a) == Y) {
			cout << "Yes" << endl;
			return 0;
		}
	}

	cout << "No" << endl;

}




Measured memory_bytes: 3632
import sys
T=input()
S=input()
Ts=set(T)
Ss=set(S)
for v in Ts:
  ind=[i for i, x in enumerate(T) if x == v]
  for i in range(len(ind)):
    if i==0:
      continue
    if not S[ind[i-1]]==S[ind[i]]:
      print("No")
      sys.exit()
for v in Ss:
  ind=[i for i, x in enumerate(S) if x == v]
  for i in range(len(ind)):
    if i==0:
      continue
    if not T[ind[i-1]]==T[ind[i]]:
      print("No")
      sys.exit()
print("Yes")

Measured memory_bytes: 11560
#include <bits/stdc++.h>
using namespace std;
 
typedef unsigned long ul;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll MOD = 1e9+7;
const double PI  = 3.14159265358;
const double EPS = 1e-8;

#define INT_MX 2147483647
#define INF ((int)1e9)
#define LLINF ((ll)1e18)
#define F first
#define S second
#define MP(x,y) make_pair(x,y)
#define sz(v) ((int)v.size())
#define rs(n) resize(n)
#define ALL(v) v.begin(),v.end()
#define reset(v) memset((v),0,sizeof(v))
#define EB emplace_back
#define PB push_back
#define PF push_front
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define vec vector
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

void solve(){
	int hp, n;
	vec<ll> dp;
	vec<pii> v;
	
	cin >> hp >> n;
	v.rs(n);
	dp.rs(hp+1);
	rep(i, n) cin >> v[i].F >> v[i].S;
	
	rep1(i, hp){
		dp[i] = INF;
		rep(j, n)
			dp[i] = min(dp[i], dp[max(0, i - v[j].F)] + v[j].S);
	}
	
	cout << dp[hp] << '\n';
	
}

int main(){
	int t = 1;
	
	while(t--){
		solve();
	}
}




Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define INF 2147483647
#define INFF 9223372036854775807
#define ll long long
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,m,n) for(int i=m;i<=n;i++)
#define ALL(N) (N.begin(),N.end())
#define de cout << "debug" << endl;
#define pb push_back
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


int main() {
    cin.tie(0);    
	ios::sync_with_stdio(false);
    ll L,R;
    cin >> L >> R;
    if(R-L > 2019){
        cout << 0 << endl;
        return 0;
    }
    L %= 2019;
    R %= 2019;
    int minv = INF;
    if(L > R) swap(L,R);
    REPP(i,L,R){
        REPP(j,i+1,R){
            minv = min(minv,(i*j)%2019);
        }
    }
    cout << minv << endl;
}

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-1; i++) cin >> A[i];
    vector<int> ans(N+1);
    for(int a : A) ans[a]++;
    for(int i=1; i<=N; i++) cout << ans[i] << endl;
    return 0;
}


Measured memory_bytes: 4844
using System;
using System.Linq;

namespace C_sharp
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                var line = Console.ReadLine().Split(' ');
                var m = int.Parse(line[0]);
                var f = int.Parse(line[1]);
                var r = int.Parse(line[2]);

                if (m == -1 && f == -1 && r == -1)
                {
                    break;
                }

                if (m == -1 || f == -1)
                {
                    Console.WriteLine("F");
                }
                else if (m + f >= 80)
                {
                    Console.WriteLine("A");
                }
                else if (m + f >= 65)
                {
                    Console.WriteLine("B");
                }
                else if (m + f >= 50)
                {
                    Console.WriteLine("C");
                }
                else if (m + f >= 30)
                {
                    if (r >= 50)
                    {
                        Console.WriteLine("C");
                    }
                    else
                    {
                        Console.WriteLine("D");
                    }
                }
                else
                {
                    Console.WriteLine("F");
                }
            }
        }
    }
}



Measured memory_bytes: 15948
#include<stdio.h>
int main(void)
{
  int a,b,tmp;

  scanf("%d%d",&a,&b);

  if(b<a){
    tmp=a;
    a=b;
    b=tmp;
  }

  if(1>a){
    return 1;
  }else if(b>20){
    return 1;
  }

  if(b%a == 0){
    printf("%d\n",a+b);
  }else{
    printf("%d\n",b-a);
  }
  return 0;
}

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

int main() {
int n;
cin>>n;
vector<int> a(n);
vector<int> anum(100000);
unsigned long long int ans=0;
for (int i = 0; i < n; i++)
{
    cin>>a[i];
    ans+=a[i];
    anum[a[i]]++;
}
int q;
cin>>q;
vector<int> b(q);
vector<int> c(q);

for (int i = 0; i < q; i++)
{
    cin>>b[i]>>c[i];
}

for (int i = 0; i < q; i++)
{
  ans+=anum[b[i]]*(c[i]-b[i]);

anum[c[i]]+=anum[b[i]];
anum[b[i]]=0;
cout<<ans<<endl;

}



}

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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int n,m; cin>>n>>m;
	vector<int>first;
	vector<bool>last(n+1,false);
	for(int i=0;i<m;++i){
		int a,b; cin>>a>>b;
		if(a==1)first.emplace_back(b);
		if(a==n)last.at(a)=true;
		else if(b==n)last.at(a)=true;
	}
	bool yes=any_of(first.begin(),first.end(),[=](auto a){return a==n||last.at(a);});
	cout<<(yes?"POSSIBLE"s:"IMPOSSIBLE"s)<<"\n"s;
}

Measured memory_bytes: 892
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;
import static java.lang.Math.*;

// Exportation in Space
// 2012/12/13
public class Main{
	Scanner sc=new Scanner(System.in);

	double EPS=1e-6;
	int n;
	P[] ps;

	void run(){
		n=sc.nextInt();
		ps=new P[n];
		for(int i=0; i<n; i++){
			double x=sc.nextInt();
			double y=sc.nextInt();
			double z=sc.nextInt();
			ps[i]=new P(x, y, z);
		}
		solve();
	}

	void solve(){
		for(int i=0; i<n; i++){
			P d=new P(random()*EPS, random()*EPS, random()*EPS);
			ps[i]=ps[i].add(d);
		}

		P[][] ch=convexHull(ps);
		double sum=0;
		for(P[] ps : ch){
			double a=ps[0].sub(ps[1]).abs();
			double b=ps[1].sub(ps[2]).abs();
			double c=ps[2].sub(ps[0]).abs();
			sum+=area(a, b, c);
		}
		println(String.format("%.12f", sum));
	}

	double area(double a, double b, double c){
		double s=(a+b+c)/2;
		return sqrt(s*(s-a)*(s-b)*(s-c));
	}

	P[][] convexHull(P[] ps){
		int n=ps.length;

		int[][] vs=new int[n][n];
		List<int[]> crt=new ArrayList<int[]>();
		crt.add(new int[]{0, 1, 2});
		crt.add(new int[]{2, 1, 0});

		for(int i=3; i<n; i++){
			List<int[]> next=new ArrayList<int[]>();
			for(int[] t : crt){
				int v=ps[t[1]].sub(ps[t[0]]).det(ps[t[2]].sub(ps[t[0]]))
						.dot(ps[i].sub(ps[t[0]]))<0?-1:1;
				if(v<0)
					next.add(t);
				for(int j=0; j<3; j++){
					if(vs[t[(j+1)%3]][t[j]]==0){
						vs[t[j]][t[(j+1)%3]]=v;
					}else{
						if(vs[t[(j+1)%3]][t[j]]!=v){
							if(v>0)
								next.add(new int[]{t[j], t[(j+1)%3], i});
							else
								next.add(new int[]{t[(j+1)%3], t[j], i});
						}
						vs[t[(j+1)%3]][t[j]]=0;
					}
				}
			}
			crt=next;
		}

		P[][] pss=new P[crt.size()][3];
		for(int i=0; i<pss.length; i++){
			for(int j=0; j<3; j++)
				pss[i][j]=ps[crt.get(i)[j]];
		}
		return pss;
	}

	class P{
		double x, y, z;

		P(double x, double y, double z){
			this.x=x;
			this.y=y;
			this.z=z;
		}

		P add(P p){
			return new P(x+p.x, y+p.y, z+p.z);
		}

		P sub(P p){
			return new P(x-p.x, y-p.y, z-p.z);
		}

		P mul(double m){
			return new P(x*m, y*m, z*m);
		}

		P div(double d){
			return new P(x/d, y/d, z/d);
		}

		double abs(){
			return sqrt(abs2());
		}

		double abs2(){
			return x*x+y*y+z*z;
		}

		double dot(P p){
			return x*p.x+y*p.y+z*p.z;
		}

		P det(P p){
			return new P(y*p.z-z*p.y, z*p.x-x*p.z, x*p.y-y*p.x);
		}
	}

	void println(String s){
		System.out.println(s);
	}

	public static void main(String[] args){
		new Main().run();
	}
}

Measured memory_bytes: 13000
#include<cstdio>
#include<algorithm>
using namespace std;
int n,a[110],sum;
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+1+n);
	for (int i=n;i>=1;i--) if ((n-i)&1) sum-=a[i];else sum+=a[i];
	printf("%d",sum);
} 

Measured memory_bytes: 128