akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pi;

#define all(x) x.begin(),x.end()
#define YES {cout << "YES\n"; return;}
#define NO {cout << "NO\n"; return;}

const int INF=INT_MAX;
const ld PI=acos(-1);//3.1415926535897932384626433
const ld E=2.71828183;
const int MOD=1e9+7;

vi bfs(vector<vi>adj,int src){
    //adjacency list, not-weighted, possibly directed ,src is 1-indexed, adj[0].size()=0!!!
    //for n vertices, adj.size()=n+1. (constructed via push_back() ).

    queue<int>q;
    q.push(src);
    vi dst(adj.size(),INF);
    dst[src]=0;
    while(!q.empty()){
        int c=q.front();
        q.pop();
        for(int nbr:adj[c]){
            if(dst[nbr]==INF){
                dst[nbr]=dst[c]+1;
                q.push(nbr);
            }
        }
    }
    return dst;
}
vi bfsParents(vector<vi>adj,int src){
    vi parents=vi(adj.size(),INF);
    parents[src]=-1;
    queue<int>q;
    q.push(src);
    vi dst(adj.size(),INF);
    dst[src]=0;
    while(!q.empty()){
        int c=q.front();
        q.pop();
        for(int nbr:adj[c]){
            if(dst[nbr]==INF){
                parents[nbr]=c;
                dst[nbr]=dst[c]+1;
                q.push(nbr);
            }
        }
    }
    return parents;
}
vi shortestPath(vector<vi>adj,int src,int dst){
    vi bfsParetns=bfsParents(adj,src);
    vi ans;
    while(src!=dst){
        if(bfsParetns[src]==INF)
            return {};
        ans.push_back(src);
        src=bfsParetns[src];
    }
    return ans;
}
int powMod(int base,int exp,int mod){
    //(base^exp) %mod
    int ans=1;
    for(int i=0; i<exp; i++)
        ans=((ans%mod)*(base%mod))%mod;
    return ans;
}
vi divisorsOf(int n){
    //vector of divisors of n (inc. 1 , excl.n)
    vi ans;
    for(int i=1; i*i<=n; i++){
        if(n%i==0)
            ans.push_back(i);
        if(i*i!=n && i!=1)
            ans.push_back(n/i);
    }
    return ans;
}

ll gcd(ll a,ll b){if(a%b==0) return b; else return gcd(b,a%b);}
ld log (ld a,ld b){return log(b)/log(a);}
ll lcm(ll a,ll b){return (a*b)/gcd(a,b);}
ll power(ll base, ll exp){ll res=1;while(exp){exp--;res*=base;}return res;}

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

    int n;
    cin >> n;
    cout << (1000-n%1000)%1000 << "\n";

}


Measured memory_bytes: 3628
void main() {
  problem();
}

void problem() {
  enum CONTESTS = 26;
  const days = scan!int;
  const dec = scan!long(CONTESTS);
  const inc = days.iota.map!(x => scan!long(CONTESTS)).array;

  long solve() {
    long[CONTESTS] desat;
    long sat;
    long prevSat;

    long decideNextContest(long day, const long[] inc, long[] dec) {
      auto maxContest = inc.maxIndex();
      return maxContest;
    }

    foreach(i; 0..days) {
      auto c = decideNextContest(i, inc[i], desat);
      (c + 1).writeln;

      sat += inc[i][c];
      foreach(o; 0..CONTESTS) {
        desat[o] = c == o ? 0 : desat[o] + dec[o];
        sat -= desat[o];
      }

      deb(["satisfaction", prevSat.to!string, "->", sat.to!string]);
      prevSat = sat;
    }
    
    return sat;
  }

  solve();
}

// ----------------------------------------------

import std.stdio, std.conv, std.array, std.string, std.algorithm, std.container, std.range, core.stdc.stdlib, std.math, std.typecons, std.numeric;
T[][] combinations(T)(T[] s, in int m) {   if (!m) return [[]];   if (s.empty) return [];   return s[1 .. $].combinations(m - 1).map!(x => s[0] ~ x).array ~ s[1 .. $].combinations(m); }
string scan(){ static string[] ss; while(!ss.length) ss = readln.chomp.split; string res = ss[0]; ss.popFront; return res; }
T scan(T)(){ return scan.to!T; }
T[] scan(T)(int n){ return n.iota.map!(i => scan!T()).array; }
void deb(T ...)(T t){ debug writeln(t); }
alias Point = Tuple!(long, "x", long, "y");

// -----------------------------------------------


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

int main()
{
    int N,M;
    bool yn = false;
    cin >> N >> M;
    char A[N][N] = {'-'};
    char B[M][M] = {'-'};

    // string A
    for(int i=0; i<N; i++)
    {
        string str;
        cin >> str;
        for(int j=0; j<N; j++)
        {
            A[i][j] = str[j];
        }
    }

    // string B
    for(int i=0; i<M; i++)
    {
        string str;
        cin >> str;
        for(int j=0; j<M; j++)
        {
            B[i][j] = str[j];
        }
    }

    for(int i=0; i<=N-M; i++)
    {
        bool b = false;
        for(int j=0; j<=N-M; j++)
        {
            bool isMatch = true;
            for(int k=0; k<M; k++)
            {
                for(int l=0; l<M; l++)
                {
                    if(A[i+k][j+l]!=B[k][l])
                        isMatch = false;
                }
            }
            if(isMatch)
            {
                yn = true;
                break;
            }
        }
        if(yn) break;
    }

    if(yn) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

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

using namespace std;

int main(void){
	int cnt = 0;
	while( true ){
		string s;
		string s1, s2;

		cin >> s;
		if( cin.eof() ) break;

		if( s.length() % 2 == 0 ){
			for(int i = 0; i < s.length() / 2; i++) s1 += s[i];
			for(int i = s.length() - 1; i >= s.length() / 2; i--) s2 += s[i];
		}else{
			for(int i = 0; i < s.length() / 2; i++) s1 += s[i];
			for(int i = s.length() - 1; i > s.length() / 2; i--) s2 += s[i];
		}

		if( s1.compare( s2 ) == 0 ) cnt++;
	}

	cout << cnt << endl;
	return 0;
}

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

int main() {
	int N;
	cin >> N;
	vector<int>L(N);
	for (int n = 0; n < N; ++n) {
		cin >> L[n];
	};
	sort(L.begin(), L.end());
	int ans = 0;
	for (int n = 0; n < N; ++n) {
		for (int m = n + 1; m < N; ++m) {
			int num = lower_bound(L.begin(), L.end(), L[n] + L[m]) - L.begin();
			ans += max(0, (num - (m+1)));
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3612
#include<bits/stdc++.h>
using namespace std;
int main(){
        int k;
        int a,b;
        bool ok = false;
        cin >> k >> a >> b;
        int s = 0;
        for(s = 0; s <= b;s += k){
                if(s >= a && s <= b){
                        ok = true;
                        break;
                }
        }
        if(ok)cout << "OK" << endl;
        else cout << "NG" << endl;
}


Measured memory_bytes: 3620
#include<iostream> 
#include<stdio.h>
#include<string>
#include<iomanip> 
#include<vector> 
#include<map> 
#include<set> 
#include<algorithm> 
#include<numeric> 
#include<limits> 
#include<bitset> 
#include<functional> 
#include<type_traits> 
#include<queue> 
#include<stack> 
#include<array> 
#include<random> 
#include<utility> 
#include<cstdlib> 
#include<ctime>
//#define _LIBCPP_DEBUG 0
//#define _GLIBCXX_DEBUG
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define all(a) (a).begin(),(a),end()
#define rep(i,n) for (int i = 0; i < (n); ++i)	
//setprecision(16)

void outi(int x) { cout << x << endl; }
void outl(ll x) { cout << x << endl; }
void outs(string x) { cout << x << endl; }
ll max(ll a, ll b) {
	ll max;
	if (a > b) max = a;
	else max = b;
	return max;
}
ll min(ll a, ll b) {
	ll min;
	if (a < b) min = a;
	else min = b;
	return min;
}
int gcd(int x, int y) {
	/*最大公約数 O(log MAX_X)*/
	if (y == 0) return x;
	return gcd(y, x % y);
}
//---------------------------------------------------------------

int main() {

	int n;
	cin >> n;
	string s;

	int countAC = 0;
	int countWA = 0;
	int countTLE = 0;
	int countRE = 0;

	rep(i, n) {
		cin >> s;
		if (s == "AC") {
			countAC++;
		}
		if (s == "WA") {
			countWA++;
		}
		if (s == "TLE") {
			countTLE++;
		}
		if (s == "RE") {
			countRE++;
		}
	}

	cout << "AC x " << countAC <<endl;
	cout << "WA x " << countWA << endl;
	cout << "TLE x " << countTLE << endl;
	cout << "RE x " << countRE << endl;
}

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

int main(){
	int n;
  	cin >> n;
  	int ar[n];
  	int count = 0;
  	for(int i = 0;i < n;i++) cin >> ar[i];
  	for(int i = 0;i < n;i++){
    	for(int j = i+1;j < n;j++){
        	for(int k = j+1;k < n;k++){
            	if(ar[i] != ar[j] && ar[j] != ar[k] && ar[i] != ar[k] && ar[i] + ar[j] > ar[k] && ar[i] + ar[k] > ar[j] && ar[j] + ar[k] > ar[i]){
                	count ++;
                }
            }
        }
    }
  	cout << count;
}


Measured memory_bytes: 3616
import java.io.PrintStream;
import java.util.Scanner;

public class Main {
	static final PrintStream out = System.out;
	static Scanner sc = new Scanner(System.in);
	static final long Mod = 1000_000_007L;
	public static void main(String[] args) {
		Main main = new Main();
		main.solve();
		System.exit(0);
	}

	void solve() {
		int N = nextInt();
		int M = nextInt();
		int[] a = new int[M+2];
		for(int i=1;i<=M;i++) {
			a[i]=nextInt();
		}
		sc.close();
		long[] dp = new long[N+1];
		int ta = 1;
		dp[0] = 1;
		if(a[ta]!=1)dp[1]=dp[0];
		else ta++;
		for(int i=2;i<=N;i++) {
			if(a[ta]!=i) {
				dp[i] = dp[i-2]+dp[i-1];
				dp[i]-=dp[i]>Mod?Mod:0;
			}else {
				ta++;
			}
		}
		out.println(dp[N]);
	}
	private static int nextInt() {
		return Integer.parseInt(next());
	}
	private static long nextLong() {
		return Long.parseLong(next());
	}
	private static String next() {
		return sc.next();
	}

}

Measured memory_bytes: 49188
import Control.Monad
import Data.Maybe
import qualified Data.ByteString.Char8 as BS
import Data.List

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine

main = do
    [n,k] <- getIntList
    let (d,m) = n `divMod` k
        ans | odd k = d^3
            | even k = d^3 + e^3
            where e = n `div` (k `div` 2) - d
    print ans

Measured memory_bytes: 380
import java.util.*;
import java.math.*;

public class Main {
    public static void main(String[] args) throws Exception {
        
        Scanner sc = new Scanner(System.in);
        BigInteger X = sc.nextBigInteger();
        BigInteger Y = sc.nextBigInteger();
        BigInteger sum = X;
        long count = 0;
        while( sum.compareTo(Y) != 1 ) {
            sum = sum.multiply( BigInteger.valueOf(2) );
            count++;
        }
        System.out.println(count);
    }
}


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

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

c = []

for i in range(n-1):
    for j in range(i+1, n):
        c.append([(p[i][0] + p[j][0]) / 2, (p[i][1] + p[j][1]) / 2])

for i in range(n-2):
    x = p[i][0] + p[i][1] * 1j
    for j in range(i+1, n-1):
        y = p[j][0] + p[j][1] * 1j
        for k in range(j+1, n):
            z = p[k][0] + p[k][1] * 1j
            a = y - x
            b = z - x
            if a.real * b.imag == a.imag * b.real:
                continue
            C = a * b * (a.conjugate() - b.conjugate()) / (b * a.conjugate() - a * b.conjugate())
            C = C + x
            c.append([C.real, C.imag])

ans = float('inf')
for X, Y in c:
    temp = 0
    for x, y in p:
        temp = max(((X-x)**2 + (Y-y)**2) ** 0.5, temp)
    ans = min(ans, temp)

print(ans)

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

signed main() {
  string S, T, x, y, xx, yy;
  cin >> S;
  int N;
  N = S.size();

  T = S;
  reverse(T.begin(), T.end());

  if (S != T) {
    cout << "No" << endl;
    return 0;
  }

  x = S.substr(0, (N - 1) / 2);
  y = S.substr((N + 3) / 2 - 1);

  xx = x;
  yy = y;

  reverse(xx.begin(), xx.end());
  reverse(yy.begin(), yy.end());

  if (x != xx || y != yy) {
    cout << "No" << endl;
    return 0;
  }

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

Measured memory_bytes: 3616
from collections import defaultdict
class Prime:
    def __init__(self,number):#N以下の素数
        self.jud=[True]*(number+5)
        self.pri=[]
        self.jud[0]=False
        self.jud[1]=False
        for i in range(number):
            if self.jud[i]:
                self.pri.append(i)
                for j in range(2,(number)//i+1):
                    self.jud[i*j]=False
    
    def judge(self,x):
        return self.jud[x]
    
    def decom(self,x):
        s=x
        a =defaultdict(int)
        if s==1:
            return a
        while s>1:
            for p in self.pri:
                if s%p==0:
                    a[p]+=1
                    s=s//p
                    break
        return a
            

A=Prime(102+5)
N=int(input())
dd=defaultdict(int)
for s in range(2,N+1):
    d1=A.decom(s)
    for p,v in d1.items():
        dd[p]+=v
ans=0
#3-5-5type
L=[0,0]
for p,v in dd.items():
    if 2<=v<4:
        L[0]+=1
    elif 4<=v:
        L[1]+=1
ans+=(L[0]*L[1]*max(L[1]-1,0))//2
ans+=(L[1]*max(L[1]-1,0)*max(L[1]-2,0))//2
#print(ans)
#15-5type
M=[0,0]
for p,v in dd.items():
    if 4<=v<14:
        M[0]+=1
    elif 14<=v:
        M[1]+=1
ans+=M[0]*M[1]
ans+=(M[1]*max(M[1]-1,0))
#print(ans)
#25-3type
N=[0,0]
for p,v in dd.items():
    if 2<=v<24:
        N[0]+=1
    elif 24<=v:
        N[1]+=1
ans+=N[0]*N[1]
ans+=(N[1]*max(N[1]-1,0))
for p,v in dd.items():
    if 74<=v:
        ans+=1
print(ans)

Measured memory_bytes: 38464
#define _CRT_SECURE_NO_WARNINGS
#pragma target("avx")
#pragma optimize("O3")
#pragma optimize("unroll-loops")
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#define rep(i,n) for(int i=0;i<(lint)(n);i++)
#define REP(i,n) for(int i=1;i<=(lint)(n);i++)
#define all(V) V.begin(),V.end()
typedef long long lint;
typedef unsigned long long ulint;
typedef std::pair<lint, lint> P;
constexpr int INF = INT_MAX/2;
constexpr lint LINF = LLONG_MAX/2;
constexpr double eps = DBL_EPSILON;
constexpr double PI=3.141592653589793238462643383279;
template<class T>
class prique :public std::priority_queue<T, std::vector<T>, std::greater<T>> {};
template <class T, class U>
inline bool chmax(T& lhs, const U& rhs) {
	if (lhs < rhs) {
		lhs = rhs;
		return 1;
	}
	return 0;
}
template <class T, class U>
inline bool chmin(T& lhs, const U& rhs) {
	if (lhs > rhs) {
		lhs = rhs;
		return 1;
	}
	return 0;
}
inline lint gcd(lint a, lint b) {
	while (b) {
		lint c = a;
		a = b; b = c % b;
	}
	return a;
}
inline lint lcm(lint a, lint b) {
	return a / gcd(a, b) * b;
}
bool isprime(lint n) {
	if (n == 1)return false;
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0)return false;
	}
	return true;
}
template<typename T>
T mypow(T a, unsigned int b) {
	if (!b)return T(1);
	if (b & 1)return mypow(a, b - 1) * a;
	T memo = mypow(a, b >> 1);
	return memo * memo;
}
lint modpow(lint a, lint b, lint m) {
	if (!b)return 1;
	if (b & 1)return modpow(a, b - 1, m) * a % m;
	lint memo = modpow(a, b >> 1, m);
	return memo * memo % m;
}
template<typename T>
void printArray(std::vector<T>& vec) {
	rep(i, vec.size() - 1)std::cout << vec[i] << " ";
	std::cout << vec.back() << std::endl;
}
template<typename T>
void printArray(T l, T r) {
	T rprev = r;
	rprev--;
	for (T i = l; i != rprev; i++) {
		std::cout << *i << " ";
	}
	std::cout << *rprev << std::endl;
}
int n,a[200010];
int m[1000010];
std::map<int,int> mp;
int main(){
	std::cin>>n;
	rep(i,n){
		std::cin>>a[i];
		mp[a[i]]++;
	}
	std::sort(a,a+n);
	int ans=0;
	rep(i,n){
		m[a[i]]++;
		if(m[a[i]]==1){
			for(int j=a[i]*2;j<=1000000;j+=a[i]){
				m[j]++;
			}
		}
	}
	rep(i,n){
		if(m[a[i]]==1&&mp[a[i]]==1)ans++;
	}
	std::cout<<ans<<std::endl;
	return 0;
}


Measured memory_bytes: 17468
#include <bits/stdc++.h>
#define rep(i,x,n) for(int i=x; i<(int)(n); i++)
#define rep_eq(i,x,n) for(int i=x; i<=(int)(n); i++)
#define all(vec) vec.begin(),vec.end()
using namespace std;

using ll=long long;

using vi=vector<int>;
using vll=vector<ll>;
using vvi=vector<vi>;
using vs=vector<string>;

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

  string S; cin >>S;
  ll ans=0;
  rep(bit,0,1<<(S.size()-1)) {
    string f="";
    rep(i,0,S.size()) {
      f+=S[i];
      if (bit&(1<<i)) {
        ans+=stoll(f);
        f="";
      }
    }
    ans+=stoll(f);
  }
  cout <<ans <<'\n';
  return 0;
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
#define fi first
#define se second
#define maxn 2001
#define mod 1000000007
#define pb push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> pi;

int n;
int dp[maxn];
int sum[maxn];

int main() {
	scanf("%d",&n);
	dp[0] = 1;
	sum[0] = sum[1] = sum[2] = 1;
	for( int i = 3 ; i <= n ; i++ ) {
		dp[i] = sum[i-3];
		sum[i] = (sum[i-1] + dp[i]) % mod;
	}
	printf("%d\n",dp[n]);
	return 0;
}

Measured memory_bytes: 3824
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;

int main() {
    int t=1;
    //cin >> t;
    while(t--){
        ll n;
        cin >> n;
        if(n%2!=0){
            cout << n/2 + 1 << endl;
        }else{
            cout << n/2 << endl;
        }
    }
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
int const nax = 3e5 + 10;
//#define LOCAL
#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...) 42
#endif // LOCAL
using ll = long long ;
int n, d[nax];
vector<int> a[nax];
int x, y, tin[nax], tout[nax], timer, up[nax][19]; /// Takahashi and Aoki respectively
void dfs(int nod, int par){
    tin[nod] = ++ timer;
    up[nod][0] = par;
    for(int i = 1 ;i <= 18 ; i ++)
        up[nod][i] = up[up[nod][i - 1]][i - 1];
    for(int i : a[nod]){
        if(i == par) continue;
        d[i] = d[nod] + 1;
        dfs(i, nod);
    }
    tout[nod] = ++ timer;
}
bool ancestor(int u, int v){
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v){
    if(ancestor(u, v)) return u;
    if(ancestor(v, u)) return  v;
    for(int i = 18 ;i  >= 0 ; i --){
        if(!ancestor(up[u][i], v)){
            u = up[u][i];
        }
    }
    return up[u][0];
}
vector<int> lf;
int dist(int u, int v){
    return d[u] + d[v] - 2 * d[lca(u, v)];
}

int main(){
    tout[0] = 1e9;
    scanf("%d %d %d", &n, &x, &y);
    for(int i =1 ; i< n; i++){
        int u, v;
        scanf("%d %d", &u, &v);
        a[u].push_back(v);
        a[v].push_back(u);
    }
    dfs(y, 0);
    for(int i = 1 ;i <= n ;i ++){
        if(i != y && (int)a[i].size() == 1)
            lf.push_back(i);
    }
    int ans = 0;
    for(int c : lf){
        int lc = lca(x, c);
        int disT = dist(x, lc);
        int disA = dist(y, lc);
        eprintf("%d Ta = %d AO = %d\n", lc, disT, disA);
        if(disA <= disT) {
            ans = max(ans, disA);
            continue;
        }
        int A = dist(c, y);
        ans = max(ans, A - 1);
    }
    eprintf("\n");
    return !printf("%d\n", ans);
}
/*
    Good Luck
        -Lucina
*/


Measured memory_bytes: 27776
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
#include<utility>
#include<string>
#include<utility>
#include<iomanip>
#include<bitset>
#include<math.h>
using namespace std;


int main(){

    int n,d;
    cin >> n >> d;
    int ans = 0;
    vector<vector<double>> v(n,vector<double>(d));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < d; j++)
        {
            int x;
            cin >> x;
            v[i][j] = x;
        }
    }
    double sum=0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < i; j++)
        {
            sum = 0;
            for (int k = 0; k < d; k++)
            {
                sum += (abs(v[i][k]-v[j][k]))*abs(v[i][k]-v[j][k]);
            }
            sum = sqrt(sum);
            if(ceil(sum) == floor(sum)){
                ans ++;
            }
        }
        
    }

    cout << ans << endl;

    
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void) {
	char a, b, c;
	//printf("文字列を入力してください\n");
	scanf("%c", &a);
	scanf("%c", &b);
	scanf("%c", &c);
	if (a == b && b == c)
		printf("No");
	else
		printf("Yes");
	return 0;
}


Measured memory_bytes: 128
import sys
def 解():
    input = sys.stdin.readline

    N,W=[int(_) for _ in input().split()]
    dp={0:0}
    for _ in range(N):
        w,v=[int(_) for _ in input().split()]
        #for j in dp.copy():
        for j in sorted(dp.keys(),reverse=True):
            nw = dp[j]+w
            nv = j+v
            if nw <= W :
                if nv in dp:
                    if nw < dp[nv]:
                        dp[nv] = nw
                else:
                    dp[nv] = nw

    print(max(dp.keys()))
解()


Measured memory_bytes: 10860
#include<bits/stdc++.h>
using namespace std;
signed main(void){
	ios::sync_with_stdio(false);
	int T;
	cin>>T;
	double x1,x2,y1,y2,r1,r2,d;
	for(int t=1;t<=T;t++){
		cin>>x1>>y1>>r1
		   >>x2>>y2>>r2;
		d=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
		if(d>r1+r2)
			cout<<0<<endl;
		else if(d<r1-r2)
			cout<<2<<endl;
		else if(d<r2-r1)
			cout<<-2<<endl;
		else
			cout<<1<<endl;
	}
}

Measured memory_bytes: 1236
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include<set>
#include<map>
using namespace std;


int main() {
    vector<string> v {"SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT"};
    string s;
    cin >> s;
    int index = find(v.begin(), v.end(), s) - v.begin();
    cout << v.size() - index;
    cout << endl;
}


Measured memory_bytes: 256
a=int(input())


import math
def combinations_count(n,r):
  return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
b=a//3
count=0
for i in range(1,b+1) :
  count+=combinations_count(a-2*i-1,i-1)
  

print(count%(10**9+7))

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

using ll = long long;
const ll INF = 1e18;

const int MAXN = 2.1e5;
int N;
int Q;
int X[MAXN];

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> N >> Q;
	int A, B; cin >> A >> B;

	for (int q = 0; q < Q; q++) { cin >> X[q]; }

	ll cval = 0;
	map<int, ll> mp;
	mp[A] = 0;
	int prevVal = B;

	auto queryPt = [&](int x) -> ll {
		ll ans = INF;
		auto it = mp.lower_bound(x);
		if (it != mp.end()) {
			ans = min(ans, (it->first - x) + it->second);
		}
		if (it != mp.begin()) {
			--it;
			ans = min(ans, (x - it->first) + it->second);
		}
		return ans;
	};

	auto insertPt = [&](int x, ll v) {
		if (v >= queryPt(x)) return;
		auto it = mp.lower_bound(x);
		while (it != mp.end()) {
			if ((it->first - x) + v <= it->second) {
				it = mp.erase(it);
			} else {
				break;
			}
		}
		while (it != mp.begin()) {
			--it;
			if ((x - it->first) + v <= it->second) {
				it = mp.erase(it);
			} else {
				break;
			}
		}
		mp[x] = v;
	};

	for (int q = 0; q < Q; q++) {
		int curVal = X[q];
		insertPt(prevVal, queryPt(curVal) - abs(prevVal - curVal));
		cval += abs(prevVal - curVal);

		prevVal = X[q];
	}
	ll ans = INF;
	for (auto it : mp) ans = min(ans, it.second);
	cout << ans + cval << '\n';


	return 0;
}


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

#ifdef LOCAL
#define DEBUG(...) debug(#__VA_ARGS__, __VA_ARGS__);
#else
#define DEBUG(...) 6;
#endif

template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) {return os << "(" << p.first << ", " << p.second << ")";}
template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator << (ostream &os, const C &c) {bool f = true; os << "["; for (const auto &x : c) {if (!f) os << ", "; f = false; os << x;} return os << "]";}
template<typename T> void debug(string s, T x) {cerr << s << " = " << x << "\n";}
template<typename T, typename... Args> void debug(string s, T x, Args... args) {cerr << s.substr(0, s.find(',')) << " = " << x << " | "; debug(s.substr(s.find(',') + 2), args...);}

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

    int s, w;
    cin >> s >> w;
    cout << (w >= s ? "unsafe" : "safe") << "\n";

    return 0;
}


Measured memory_bytes: 3568
#include <iostream>
#include <algorithm>
#include <vector>
typedef long long ll;
using namespace std;

int main() {
	int x, y;
	cin >> x >> y;
	int xg, yg;
	if (x == 2)
		xg = 3;
	else if (x == 4 || x == 6 || x == 9 || x == 11)
		xg = 2;
	else
		xg = 1;
	if (y == 2)
		yg = 3;
	else if (y == 4 || y == 6 || y == 9 || y == 11)
		yg = 2;
	else
		yg = 1;
	if (xg == yg)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> vvl;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvec;
typedef vector<vector<bool>> vveb;
typedef vector<vector<string>> vves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pb push_back
#define pp pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
typedef long long int64;
//const int64 INF = 1LL << 58;
#define dame { puts("-1"); return 0;}
#define YES { cout << "YES" << endl; return 0; }
#define NO { cout << "NO" << endl; return 0; }
#define Yes { cout << "Yes" << endl; return 0; }
#define No { cout << "No" << endl; return 0; }
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 (a>b) { a=b; return 1; } return 0; }
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};
int n,m;
vi a;
ll cnt = 0;


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

    int a,p;
    cin >> a >> p;
    cout << (a*3+p)/2 << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define X first
#define Y second
#define clr(u,v); memset(u,v,sizeof(u));
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=1e6+10;
const int INF=0x3f3f3f3f;

int main()
{
    int n;
    ll T,A,t=0,a=0;
    scanf("%d",&n);
    while (n--)
    {
        cin>>T>>A;
        if (T<t||A<a)
        {
            ll add=max((t+T-1)/T,(a+A-1)/A);
//            cout<<add<<endl;
            t=add*T;
            a=add*A;
        }
        else t=T,a=A;
        //printf("t %I64d a %I64d\n",t,a);
    }
    cout<<t+a<<endl;
    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define N 100020
#define ll long long
using namespace std;
inline int read(){
  int x=0,f=1;char ch=getchar();
  while(ch>'9'||ch<'0')ch=='-'&&(f=0)||(ch=getchar());
  while(ch<='9'&&ch>='0')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
  return f?x:-x;
}
ll f[N], x[N];
int main(int argc, char const *argv[]) {
  // freopen("D:/1_00.txt", "r", stdin);

  int n = read();
  ll E = read(), T = read();

  for (int i = 1; i <= n; ++ i) {
    x[i] = read();
  }

  memset(f, 0x3f, sizeof f);
  f[0] = 0;

  ll mn = 1ll << 60;
  for (int i = 1, j = 0; i <= n; ++ i) {
    while (T <= 2 * (x[i] - x[j + 1])) {
      mn = min(mn, f[j] - 2 * x[j + 1]);
      ++ j;
    }
    f[i] = min(f[j] + T, mn + 2 * x[i]);
  }

  printf("%lld\n", f[n] + E);

  return 0;
}
/*

只有两种情况。

          | wait T )
----------+------------>
0         A            B            E


-----------------------.
          .------------`
          `--------------->
0         A            B            E

dp 计算需要多走多少时间即可。

*/

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

int main() {
  int n;
  cin >> n;
  int ans = 100000;

  for(int i = 0; i < n; i++){
    int num;
    cin >> num;
    int cnt = 0;

    while(num % 2 == 0){
      num /= 2;
      cnt++;
    }

    ans = min(ans, cnt);
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void){
	char in[5];
	scanf("%s", in);
	for(int i = 0; i < 3; i++){
		if(in[i] == in[i + 1]){
			printf("Bad\n");
			return 0;
		}
	}
	printf("Good\n");
	return 0;
}


Measured memory_bytes: 128
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        long sum = 0;
        Map<Integer, Long> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            map.put(a[i], map.getOrDefault(a[i], 0L) + 1);
            sum += a[i];
        }
        int q = sc.nextInt();
        int[] b = new int[q];
        int[] c = new int[q];
        for (int i = 0; i < q; i++) {
            b[i] = sc.nextInt();
            c[i] = sc.nextInt();
        }
        for (int i = 0; i < q; i++) {
            if (!map.containsKey(b[i])) {
                map.put(b[i], 0L);
            }
            long bcnt = map.get(b[i]);
            if (!map.containsKey(c[i])) {
                map.put(c[i], 0L);
            }
            long ccnt = map.get(c[i]);
            map.put(b[i], 0L);
            map.put(c[i], ccnt + bcnt);
            sum += c[i] * bcnt - b[i] * bcnt;
            System.out.println(sum);
        }

    }

}


Measured memory_bytes: 82256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<iomanip>
#include<cmath>
#define pi 3.14159265358979323846
#define mod 1000000007
#define int long long
#define elif else if
#define rep(i, a, n) for(int i = a; i < n; i++)
using namespace std;
signed main(){
  int a, b;
  cin >> a >> b;
  
  if(b > a){
    int d = b;
    b = a;
    a = d;
  }
  //cout << a << " "<< b << "\n";
  int c = b,e = 1;
  rep(i, 0, a - 1){
    e = e * 10;
    c += b * e;
  }
  cout << c << "\n";
}
      

Measured memory_bytes: 3560
#include <bits/stdc++.h>
using namespace std;
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(int i = int(a); i < int(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define all(x) (x).begin(), (x).end()
typedef long long lint;
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(a > b) {
        a = b;
        return 1;
    }
    return 0;
}
/* templates */ /* templates */ /* templates */ /* templates */ /* templates */

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

    int N;
    cin >> N;
    int H[N];
    rep(i, N) { cin >> H[i]; }
    int tmpmax = 0, ans = 0;
    rep(i, N) {
        if(H[i] >= tmpmax) {
            ans++;
        }
        chmax(tmpmax, H[i]);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int search(int A[], int n, int key){
int i = 0;
A[n] = key;
while(A[i] != key) i++;
return i != n;
}
int main(){
int i, n, A[10000+1], q, key, sum = 0;
scanf("%d", &n);
for(i = 0; i < n; i++) scanf("%d", &A[i]);
scanf("%d", &q);
for(i = 0; i < q; i++){
scanf("%d", &key);
if(search(A, n, key)) sum++;
}
printf("%d\n", sum);
return 0;
}


Measured memory_bytes: 2732
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <algorithm>
#include <cassert>
#include <cfloat>
#include <complex>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define repLRE(i, l, r) for (ll i = (l); i <= (r); ++i)
#define rrepLRE(i, l, r) for (ll i = (l); i >= (r); --i)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define Lower_bound(v, x) \
  distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) \
  distance(v.begin(), upper_bound(v.begin(), v.end(), x))

using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;
using T = tuple<ll, ll, ll>;
using vll = vector<ll>;
using vP = vector<P>;
using vT = vector<T>;
using vvll = vector<vector<ll>>;
using vvP = vector<vector<P>>;
using dqll = deque<ll>;

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

/* Macros reg. ends here */

const ll INF = 1LL << 50;

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cout << fixed << setprecision(15);

  string s;
  cin >> s;
  ll n = s.size();
  string ans = "Yes";
  rep(i, n/2) if (s[i] != s[n - 1 - i]) ans = "No";

  cout << ans << endl;

  return 0;
}


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

int main() {
    int n,m;
    cin >> n >> m;
    pair<int,int> p[m];
    for(int i = 0; i < m; i++) {
        cin >> p[i].second >> p[i].first;
    }
    sort(p,p+m);
    int MAX=0;
    int ans=0;
    for(int i=0;i<m;i++){
        if(p[i].second>MAX){
            ans++;
            MAX=p[i].first-1;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 1024
#include<iostream>
#define MAX_N 100001
using namespace std;
typedef long long ll;

ll A[MAX_N], B[MAX_N];

int main() {
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) cin >> A[i] >> B[i];
    ll ans = 0;
    for (int i = N - 1; i >= 0; i--) {
        ll tmp = A[i] + ans;
        ans += (tmp % B[i] == 0 ? tmp : (tmp / B[i] + 1) * B[i]) - tmp;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1792
#include<stdio.h>
#define MAX 100

int main(void)
{
  int N,M,X,Y;
  int x[MAX];
  int y[MAX];
  int i,min=101,max=-101;

  scanf("%d",&N);
  scanf("%d",&M);
  scanf("%d",&X);
  scanf("%d",&Y);
  for(i=0;i<N;i++){
    scanf("%d",&x[i]);
    if(max<x[i]){max=x[i];}
  }
  for(i=0;i<M;i++){
    scanf("%d",&y[i]);
    if(min>=y[i]){min=y[i];}
  }
  if(max>X&&min<=Y&&min>max){
    printf("No War\n");
  }
  else{printf("War\n");}


  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<n;++i)
#include<string>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<int, int>P;
//max=({});
//条件式が真ならwhileの中身を回し続ける
//printf("%d\n", ans);

//pairの入力
//vector<pair<ll, ll>>work(n);
//rep(i, n) {
//	ll a, b;
//	cin >> a >> b;
//	work[i] = make_pair(a, b);
//}

int g[15][15];
const int INF = 1001001001;
const int dx[4] = { -1,0,1,0 };
const int dy[4] = { 0,-1,0,1 };

//最大公約数
ll gcd(ll x, ll y) {
	return y ? gcd(y, x % y) : x;
}

//素因数分解
vector<pair<ll, int>>factorize(ll n) {
	vector<pair<ll, int>>res;
	for (ll i = 2;i * i <= n;++i) {
		if (n % i)continue;
		res.emplace_back(i, 0);
		while (n % i == 0) {
			n /= i;
			res.back().second++;
		}
	}
	if (n != 1)res.emplace_back(n, 1);
	return res;
}

int dp[1010][1010];
int bingo[3][3];
bool flag[3][3];

int main() {
	ll h, w;
	cin >> h >> w;
	ll ans = (h * w + 1) / 2;
	if (h == 1 || w == 1)cout << 1 << endl;
	else cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define ff              first
#define fo(i,n)         for(i=0;i<n;i++)
#define Fo(i,k,n)       for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define deb(x)          cout << #x << "=" << x << endl
#define deb2(x, y)      cout << #x << "=" << x << "," << #y << "=" << y << endl
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define w(x)            int x; cin>>x; while(x--)
#define FIO             ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

const int N = 3e5, M = N;
//=======================

vi g[N];

void solve() {
	int i, j, n, m;
	cin >> n;
	if (n % 2 == 0) {
		cout << -1;
		return ;
	}
	int r = 0;
	bool start = 1;
	i = 0;
	unordered_set<int> s;
	while (r || start) {
		r = (r * 10 + 7) % n;
		auto it = s.find(r);
		if (it != s.end()) {

			cout << -1;
			return ;
		}
		s.insert(r);
		i++;
		start = 0;
	}
	cout << i;
}

int32_t main()
{
	FIO;
#ifndef ONLINE_JUDGE
	freopen("input1.txt", "r", stdin);
	freopen("output1.txt", "w", stdout);
#endif
	solve();
	return 0;
}

void ipgraph(int n, int m) {
	int i, u, v;
	while (m--) {
		cin >> u >> v;
		u--, v--;
		g[u].pb(v);
		g[v].pb(u);
	}
}

void dfs(int u, int par) {
	for (int v : g[u]) {
		if (v == par) continue;
		dfs(v, u);
	}
}

Measured memory_bytes: 49712
#![allow(dead_code)]

fn main() {
    let n: Vec<u32> = read_vec();

    let num = n[0];
    let leg = n[1];

    let mut flg = 0;

    if 4*num < leg {
        println!("No");
    }else {
        for i in (0..num + 1) {
            let legs = 2 * i + 4 * (num - i);

            if legs == leg {
                flg = 1;
                break;
            }
        }

        if flg == 0 {
            println!("No");
        } else {
            println!("Yes");
        }
    }
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

fn read_n<T: std::str::FromStr>(n: u32) -> Vec<T> {
    (0..n).map(|_| read()).collect()
}


Measured memory_bytes: 2164
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define setp(x) cout<<fixed<<setprecision(x)
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define F first
#define S second
#define pqueue priority_queue
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
void amin(ll &a, ll b){ a=min(a,b); }
void amax(ll &a, ll b){ a=max(a,b); }
void SD(int t=0){ cout<<"PASSED "<<t<<endl; }
const ll INF = ll(1e18);
const int MOD = 998244353;

const int MAXN = 100005;

ll a,b,c,d;
ll eval(ll n){
	if(n<=0) return 0;
	
	return n-(n/c+n/d-n/((c*d)/__gcd(c,d)));
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	cin>>a>>b>>c>>d;
	cout<<eval(b)-eval(a-1)<<'\n';
	
	return 0;
}


Measured memory_bytes: 3644
#include<iostream>
#include<vector>
using namespace std;
typedef struct position{
  int x, y;
}position;
vector<vector<int> > ans2;
bool fit(vector<vector<int> > &ans, position lu, int h, int w, int val){
  for (int i = lu.y; i < lu.y + h; i++) {
    for (int j = lu.x; j < lu.x + w; j++) {
      if(ans[i][j] != 0 and ans[i][j] != val) return false;
    }
  }
  return true;
}
         
bool range(position p, int h, int w, int mh, int mw){
  return ((0 <= p.x and p.x + w - 1 < mw) and
          (0 <= p.y and p.y + h - 1 < mh));
}
           
int dfs(vector<vector<int> > &land,
        vector<vector<int> >  &ans,
         vector<int> &b,
         vector<int> &k,
         vector<position> &s,
         int depth = 0){
  if(depth == b.size()){
    if(ans2[0][0] != -1) return 100;
    ans2 = ans;
    return 1; 
  }
  // std::cout << depth << std::endl;
  int res = 0;
  for (int i = 0; i < k[depth]; i++) {
    int h = 1 + i, w = k[depth]/(i + 1);
    if((k[depth]%(i + 1)) != 0) continue;
    for (int j = 0; j < k[depth]; j++) {
      position lu = s[b[depth]];
      lu.x -= j%w;
      lu.y -= j/w;
      // std::cout << "lu.x:" << lu.x << " lu.y:" << lu.y << std::endl;
      // std::cout << "h:" << h << " w:" << w << std::endl;
      // std::cout << "range:" << range(lu, h, w, land.size(), land[0].size()) << std::endl;
      if(not range(lu, h, w, land.size(), land[0].size())) continue;
      if(fit(ans, lu, h, w, b[depth])) {
        // ansの更新
        for (int k = lu.y; k < lu.y + h; k++) 
          for (int l = lu.x; l < lu.x + w; l++) 
            ans[k][l] = b[depth];

        // for (int i = 0; i < ans.size(); i++) {
        //   for (int j = 0; j < ans[i].size(); j++) {
        //     std::cout << ans[i][j];
        //     if(j != ans[i].size() - 1) std::cout << " ";
        //     else std::cout << std::endl;
        //   }
        // }
        // std::cout << std::endl;

        res += dfs(land, ans, b, k, s, depth + 1);
        // ansを戻す．
        for (int k = lu.y; k < lu.y + h; k++) {
          for (int l = lu.x; l < lu.x + w; l++) {
            ans[k][l] = 0;
            if(k == s[b[depth]].y and l == s[b[depth]].x)ans[k][l] = b[depth];
          }
        }
      }
    }
  }
  return res;
}

int main(){
  int x, y, n;
  ans2.resize(1);
  ans2[0].resize(1, -1);
  while(std::cin >> x >> y >> n){
    if(x == 0) break;
    ans2[0][0] = -1;
    vector<int> b(n), k(n);
    vector<position> s(n + 1, position{-1, -1});
    vector<vector<int> > land(y, vector<int>(x));
    for (int i = 0; i < n; i++) {
      std::cin >> b[i] >> k[i];
    }
    for (int i = 0; i < y; i++) {
      for (int j = 0; j < x; j++) {
        std::cin >> land[i][j];
        if(land[i][j] != 0) s[land[i][j]] = position{j, i};
      }
    }
    vector<vector<int> > ans = land;
    if(dfs(land, ans, b, k, s) == 1){
      for (int i = 0; i < y; i++) {
        for (int j = 0; j < x; j++) {
          std::cout << ans2[i][j];
          if(j != x - 1) std::cout << " ";
          else std::cout << std::endl;
        }
      }
    }else{
      std::cout << "NA" << std::endl;
    }
  }
  return 0;
}



Measured memory_bytes: 3160
import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    long N = sc.nextLong();
    long ans = 0;

    for (int a = 1; a <= N; a++) {
      for (int b = 1; b <= N; b++) {
        for (int c = 1; c <= N; c++) {
          gcd(a, b);
          gcd(gcd(a, b), c);
          ans = ans + gcd(gcd(a, b), c);
        }
      }
    }
    System.out.println(ans);
  }

  private static int gcd(int i, int j) {
    if(i < j) return gcd(j, i);
    if(j == 0) return i;
    return gcd(j, i % j);
  }
}

Measured memory_bytes: 36660
#include <stdio.h>
#include <stdlib.h>
int cmpint(const void *x, const void *y) { return *(int *)y - *(int *)x; }
int main() {
	int n, k, numA[200000] = {0}, a, cnt = 0, ans = 0;
	scanf("%d%d", &n, &k);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a);
		numA[a]++;
	}

	qsort(numA, n + 1, sizeof(int), cmpint);
	for (int i = 0; i <= n; i++) {
		if (numA[i] != 0) {
			cnt++;
		}
		if (k < cnt) {
			ans += numA[i];
		}
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 1788
import java.io.*;
import java.util.*;

class Main {

	static class Dinic {
		private List<Edge>[] g;
		private int[] level;
		private int[] iterator;

		class Edge {
			int to;
			int cap;
			int residualId;

			public Edge(int to, int cap, int residualId) {
				this.to = to;
				this.cap = cap;
				this.residualId = residualId;
			}
		}

		public Dinic(int n) {
			g = new ArrayList[n];
			level = new int[n];
			iterator = new int[n];
			for (int i = 0; i < g.length; i++) {
				g[i] = new ArrayList<>();
			}
		}

		public void addEdge(int from, int to, int cap) {
			g[from].add(new Edge(to, cap, g[to].size()));
			g[to].add(new Edge(from, 0, g[from].size() - 1)); // residual path
		}

		public long maxFlow(int s, int t) {
			long flow = 0;
			while (true) {
				bfs(s);
				if (level[t] < 0) break;
				Arrays.fill(iterator, 0);
				while (true) {
					long f = dfs(s, t, Long.MAX_VALUE);
					if (f == 0) break;
					flow += f;
				}
			}
			return flow;
		}

		private void bfs(int s) {
			Arrays.fill(level, -1);
			Queue<Integer> q = new LinkedList<>();
			level[s] = 0;
			q.offer(s);
			while (!q.isEmpty()) {
				int v = q.poll();
				for (int i = 0; i < g[v].size(); i++) {
					Edge e = g[v].get(i);
					if (e.cap > 0 && level[e.to] < 0) {
						level[e.to] = level[v] + 1;
						q.offer(e.to);
					}

				}
			}
		}

		private long dfs(int s, int t, long f) {
			if (s == t) return f;
			for (int i = iterator[s]; i < g[s].size(); i = ++iterator[s]) {
				Edge e = g[s].get(i);
				if (e.cap > 0 && level[s] < level[e.to]) {
					long d = dfs(e.to, t, Math.min(e.cap, f));
					if (d > 0) {
						e.cap -= d;
						g[e.to].get(e.residualId).cap += d;
						return d;
					}
				}
			}
			return 0;
		}
	}

	public static void main(String[] args) throws Exception {
		final Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		Dinic dinic = new Dinic(n * 2 + 2);
		for (int i = 0; i < n; i++) {
			dinic.addEdge(2 * n, i, 1);
			dinic.addEdge(i + n, 2 * n + 1, 1);
		}

		int[][] a = new int[n][2];
		int[][] b = new int[n][2];
		for (int i = 0; i < n; i++) {
			a[i][0] = sc.nextInt();
			a[i][1] = sc.nextInt();
		}
		for (int i = 0; i < n; i++) {
			b[i][0] = sc.nextInt();
			b[i][1] = sc.nextInt();
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (a[i][0] < b[j][0] && a[i][1] < b[j][1]) {
					dinic.addEdge(i, n + j, 1);
				}
			}
		}

		System.out.println(dinic.maxFlow(2 * n, 2 * n + 1));
	}
}


Measured memory_bytes: 24388
import sys

s=input()
k=int(input())


s=list(s)

c=0
for i in range(len(s)):
        if s[i]=='1':
                c+=1
if c==len(s):
        print('1')
        sys.exit()

d=0
if len(s)>=k:
        for i in range(k):
                if s[i]=='1':
                        d+=1
if d==k:
        print('1')
        sys.exit()

for i in range(len(s)):
        if s[i]!='1':
                print(s[i])
                sys.exit()

Measured memory_bytes: 9196
n = int(input())
ans = 0
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr

if n >= 105:
  for i in range(105,n+1,2):
    chk = factorization(i)
    t = 1
    for j in chk:
      t *= (j[1]+1)
    if t == 8:
      ans += 1

print(ans)

Measured memory_bytes: 3064
#include<stdio.h>

#define MAX_NUM_OF_PACKS 100000
#define MAX_WEIGHT_OF_A_PACK 10000
#define MAX_TOTAL_WEIGHT MAX_NUM_OF_PACKS * MAX_WEIGHT_OF_A_PACK

int n, k, W[MAX_NUM_OF_PACKS];

bool valid(int p, int ck, int ci) {
  if (ci >= n) return true;
  if (ck >= k || p < W[ci]) return false;

  int tp = p;
  while(tp >= W[ci] && ci < n) {
    tp -= W[ci];
    ci++;
  }

  return valid(p, ck + 1, ci);
}

int minimum(int left, int right) {
  int mid = (left + right) / 2;
  bool result = valid(mid, 0, 0);
  if( mid == left && result) return mid;
  if (result) return minimum(left, mid);
  else return minimum(mid + 1, right);
}

int main() {

  scanf("%d %d", &n, &k);
  for( int i = 0; i < n; i++ ) scanf("%d", &W[i]);

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



Measured memory_bytes: 3112