akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
using namespace std;

typedef long long ll;
typedef double db;
typedef long double ldb;

template<class T> inline void checkmin(T &a,const T &b){if(b<a) a=b;}
template<class T> inline void checkmax(T &a,const T &b){if(b>a) a=b;}

const int inf=1e9+10;
const int maxn=2e5+10;

const ll base=1e9+7;
const ll mod=2038077799;

ll ha,hb,a[maxn],b[maxn],difa[maxn],difb[maxn];
int n; 

ll getval(ll x,ll k,ll mod){
	if(k==0) return 1ll;
	if(k==1) return x;
	ll res=getval(x,k/2,mod);
	res=(res*res)%mod;
	if(k&1) res=(res*x)%mod;
	return res;
}

int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++) scanf("%lld",&a[i]);
	for(int i=0;i<n;i++) scanf("%lld",&b[i]);
	for(int i=0;i<n;i++) difa[i]=a[i]^a[(i+1)%n];
	for(int i=0;i<n;i++) difb[i]=b[i]^b[(i+1)%n];
	ha=hb=0;
	for(int i=0;i<n;i++){
		ha*=base; ha%=mod;
		ha+=difa[i]; ha%=mod;
	}
	for(int i=0;i<n;i++){
		hb*=base; hb%=mod;
		hb+=difb[i]; hb%=mod;
	}
	ll val=getval(base,n-1,mod);
	vector <int> ans;
	for(int i=0;i<n;i++){
		if(ha==hb){
			ans.pb(i);  
		}
		ll now=val*difa[i]; now%=mod;
		ha+=mod-now; ha%=mod;
		ha*=base; ha%=mod;
		ha+=difa[i]; ha%=mod; 
	}
	for(int i=0;i<ans.size();i++){
		cout<<ans[i]<<" "<<(a[0]^b[(n-ans[i])%n])<<endl;
	}
	return 0;
}


Measured memory_bytes: 10612
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repr(i, a, n) for (int i = n - 1; i >= a; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

vector<vector<int>> g;
vector<int> ta, ao;

void dfs(int node, int cost, bool t) {
  if (t)
    ta[node] = cost;
  else
    ao[node] = cost;
  for (auto gg : g[node]) {
    if (t) {
      if (ta[gg] != -1)
        continue;
      dfs(gg, cost + 1, t);
    } else {
      if (ao[gg] != -1)
        continue;
      dfs(gg, cost + 1, t);
    }
  }
}

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

  int n, u, v;
  cin >> n >> u >> v;
  u--, v--;
  g.resize(n);

  rep(i, 0, n - 1) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }

  ta.resize(n, -1);
  ao.resize(n, -1);

  dfs(u, 0, true);
  dfs(v, 0, false);

  int ans = 0, count = 0, ind = -1;
  rep(i, 0, n) if (ta[i] == 1) {
    count++;
    ind = i;
  }
  if (count == 1 && ind == v)
    cout << 0 << endl;
  else {
    rep(i, 0, n) if (ta[i] < ao[i]) chmax(ans, ao[i]);
    cout << ans - 1 << endl;
  }
}


Measured memory_bytes: 10368
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<queue>
#include<bitset>
#include<cmath>
#include<complex>

using namespace std;
typedef pair<int, int> P;
typedef long long ll;

const int MAX_V = 10000;
struct edge {};
vector<edge> G[MAX_V];

// ??§????????°INF
#define INF (1<<30)
// ?¨±?????????????????
#define EPS (1e-10)
// 2??????????????????????????????????????????
#define EQ(a,b) (abs((a)-(b)) < EPS)

int main()
{
	cin.tie(0);
	ios::ios_base::sync_with_stdio(false);
	int D, N;
	while (true) {
		cin >> D >> N; if (D == 0 && N == 0)break;
		vector<int> a(N), e(N), r(N);
		for (int i = 0; i < N; ++i) {
			cin >> a[i] >> e[i] >> r[i];
		}
		vector<vector<int>>dp(D+1,vector<int>(101,INF));
		dp[D][0] = 0;
		for (int i = D; i >= 0; --i) {
			for (int j = 0; j < 101; ++j) {
				if (dp[i][j] == INF)continue;
				for (int k = 0; k < N; ++k) {
					if (j < r[k])continue;
					int tmp_i = max(0, i - a[k]), tmp_j = min(100, j + e[k]);
					dp[tmp_i][tmp_j] = min(dp[tmp_i][tmp_j], dp[i][j] + 1);
				}
			}
		}
		int ans = INF;
		for (int i = 0; i < 101; ++i)ans = min(ans, dp[0][i]);
		if (ans == INF) {
			cout << "NA" << endl;
			continue;
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 1504
#include <bit>
#include <bitset>
#include <assert.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <stdlib.h>
#include <queue>
#include <stack>


typedef long double ld;
typedef long long ll;

using namespace std;

int main() {
	int n, k;
	cin >> n >> k;
	if (k > (n + 1) / 2) {
		cout << "NO" << endl;
	} else {
		cout << "YES" << endl;
	}

	return 0;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
  
int main()
{
  ll N,M;
  cin >> N >> M;

  vector<pair<ll,string>> A(M);
  REP(i, M){
    cin >> A.at(i).first >> A.at(i).second;
  }
  ll wa= 0;
  ll ac = 0;

  vector<int> B(N,0);
  vector<int> C(N,0);

  REP(i,M){
    if(A.at(i).second == "WA"){
      if(B.at(A.at(i).first-1) == 0){
        C.at(A.at(i).first-1)++;
      }
    }else if(A.at(i).second == "AC"){
      if(B.at(A.at(i).first-1)==0){
        wa+=C.at(A.at(i).first-1);
        ac++;
        B.at(A.at(i).first-1) = 1;
      }
    }
  }

  cout << ac << " " << wa << endl;
}

Measured memory_bytes: 7296
#define _USE_MATH_DEFINES
#include<iostream>
#include<string>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<bitset>
#include<unordered_map>
#include<climits>
#include<fstream>
using namespace std;
///////////////////library zone!!!!!!!!!!!!!!!!!!!!!!!!!!!!
typedef long long ll;
typedef long double ld;
#define all(a) (a).begin(),(a).end()
#define EPS (1e-5)
#define bit(n,k) ((n>>k)&1)
const ll Mod = 1000000007;
const ll mod = 998244353;
struct H {
	ll x, y;
	bool operator<(const H &b) const {
		if (x != b.x) return x < b.x;
		return y < b.y;
	}
	bool operator>(const H &b) const {
		if (x != b.x) return x > b.x;
		return y > b.y;
	}
	bool operator==(const H &b) const { return x == b.x&&y == b.y; }
	bool operator!=(const H &b) const { return (*this) != b; }
};
struct P {
	ll pos, cost;
	bool operator<(const P &b) const { return cost < b.cost; }
	bool operator>(const P &b) const { return cost > b.cost; }
};
struct B {
	ll to, cost;
};
struct E {
	ll from, to, cost;
	bool operator<(const E &b) const { return cost < b.cost; }
	bool operator>(const E &b) const { return cost > b.cost; }
};
template<typename T, typename U>
void chmin(T &a, U b) {
	if (a > b) a = b;
}
template<typename T, typename U>
void chmax(T &a, U b) {
	if (a < b) a = b;
}
template<typename T>
T max_0(T a) {
	if (a < 0) return 0;
	return a;
}
template<typename T>
T min_0(T a) {
	if (a > 0) return 0;
	return a;
}
ll read() {
	ll u;
	ll k = scanf("%lld", &u);
	return u;
}
ll gcd(ll i, ll j) {
	if (i > j) swap(i, j);
	if (i == 0) return j;
	return gcd(j%i, i);
}
ll mod_pow(ll x, ll n, ll p) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res * x % p;
		x = x * x % p;
		n >>= 1;
	}
	return res;
}//x^n%p
vector<string>split(string s, char c = ' ') {
	vector<string>vec;
	string h = "";
	for (int i = 0; i < s.size();) {
		int j = i;
		while (j < s.size() && s[j] != ' ') {
			h += s[j++];
		}
		if (h.size() > 0) vec.push_back(h);
		h = "";
		i = j + 1;
	}
	return vec;
}
const ll Inf = 3023372036854775807;
const int inf = 1500000000;
#define int long long
//----------------------------------------------------
signed main() {
	int a, b;
	cin >> a >> b;
	if (a == b)  cout << a + b << endl;
	else cout << max(a, b) + max(a, b) - 1 << endl;
}

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


int main(){
    int64_t N;
    std::cin >> N;

    // i % j (j > i) = i
    // Search k(1<=k<N) where (N % k) > k
    // what is the max value of N % k
    // ... k = (n/2 +1) -> N % k = N/2(odd) or N/2-1(even)
    // at odd: N/2 is the same value that N/2 + 1 can maximize (N/2 % (N/2+1))
    //  -> no meaning to use N/2 + 1 for deviding N.
    // at even: N/2 -1 < N/2 % (N/2+1)
    //  -> should not use N/2 + 1 for deviding N.
    int64_t sum = 0;
    for(int64_t i = 1; i < N; i++){
        sum += i;
    }
    std::cout << sum;

}


Measured memory_bytes: 256
#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

#define FASTIO
#define ALL(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)

#ifdef FASTIO
#define scanf abacaba
#define printf abacaba
#endif

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;


/*
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
*/
string s;
int n;
vector<pair<int, int>> ed;
void add_edge(int a, int b) {
	ed.emplace_back(a, b);
}

int main() {
#ifdef FASTIO
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#endif
	cin >> s;
	n = s.size();
	s = string(1, '0') + s;
	for (int i = 0; i < s.size(); ++i)
		if (s[i] != s[n - i]) {
			cout << -1 << "\n";
			return 0;
		}
	if (s[1] == '0') {
		cout << -1 << "\n";
		return 0;
	}
	int cc = 2;
	int root = 1;
	s[n] = '1';
	for (int i = 2; i <= n; ++i) {
		if (s[i] == '1') {
			add_edge(root, i);
			while (cc != i)
				add_edge(cc, i), ++cc;
			++cc;
			root = i;
		}
	}
	for (auto p: ed)
		cout << p.first << " " << p.second << "\n";
	return 0;
}




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

int main(void) {
	int N;
	string S;
	scanf("%d", &N);
	cin >> S;

	int ans = 0;
	for (int i = 0; i < N; i++) {
		if (S.substr(i, 3) == "ABC") {
			ans++;
		}
	}

	printf("%d", ans);

	return 0;
}


Measured memory_bytes: 3756
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     @hamayanhamayan
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　⊃
---------------------------------------------------------------------------------------------------*/

int N, H[101010];
bool checked[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> H[i];

    int ans = 0;
    rep(i, 0, N) if(!checked[i]) {
        checked[i] = true;
        rep(j, i + 1, N) {
            if(H[j - 1] < H[j])
                break;
            checked[j] = true;
            chmax(ans, j - i);
        }
    }
    cout << ans << endl;
}



Measured memory_bytes: 892
height, width = map(int, input().split())

arr = []

for i in range(height):
    s = input()
    a = []
    for j in range(width):
        if s[j] == '#':
            a.append(1)
        else:
            a.append(0)
    arr.append(a)
    
h = 0
w = 0
f = 1

if arr[0][0] == 0:
    h = height-1
    w = width-1
    f = 0

while h < height-1 or w < width-1:
    if h == height-1:
        if arr[h][w+1] == 0:
            f = 0
            break
        else:
            arr[h][w+1] = 0
            w += 1
    elif w == width-1:
        if arr[h+1][w] == 0:
            f = 0
            break
        else:
            arr[h+1][w] = 0
            h += 1
    else:
        if arr[h][w+1] == 0:
            if arr[h+1][w] == 0:
                f = 0
                break
            else:
                arr[h+1][w] = 0
                h += 1
        else:
            if arr[h+1][w] == 1:
                f = 0
                break
            else:
                arr[h][w+1] = 0
                w += 1


if f == 0:
    print('Impossible')
else:
    extra = 0
    for i in range(height):
        for j in range(width):
            extra += arr[i][j]
    if extra > 1:
        print('Impossible')
    else:
        print('Possible')

Measured memory_bytes: 3064
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctype.h>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;

#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define lengthof(x) (sizeof(x) / sizeof(*(x)))
#define FILL(ptr, value) FILL_((ptr), sizeof(ptr)/sizeof(value), (value))
template <typename T>
void FILL_(void * ptr, size_t size, T value){
  std::fill((T*)ptr, (T*)ptr+size, value);
}
//4方向ベクトル→↑←↓
int dx[] ={1,0,-1,0};
int dy[] ={0,-1,0,1};
#define INF 1000000
int d[501][501];
int main()
{
  int n,m;
  while(cin>>n>>m,n||m){
  for(int i = 0;i <=n;i++){
    for(int j = 0;j <=n;j++){
      d[i][j] = INF;
    }
  }
  d[1][1] = 0;
  int x,y;
  for(int i = 0;i < m;i++){
    cin>>x>>y;
    d[x][y] = 1;
    d[y][x] = 1;
  }
  for(int i = 0;i <=n;i++){
    for(int j = 0;j <=n;j++){
      for(int k = 0;k <=n;k++){
	d[i][j] =min(d[i][j],d[i][k]+d[k][j]);
      }
    }
  }
  int ans = 0;
  for(int i = 2;i <=n;i++){
    if(d[1][i] <=2){
      ans++;
    }
  }
  cout <<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 2140
#https://atcoder.jp/contests/abc113/tasks/abc113_b

n=int(input())
t,a=map(int,input().split())
hlist=list(map(int,input().split()))
maingap=10000
answer=0

for i in range(n):
	tmp=t-0.006*hlist[i]
	gap=abs(tmp-a)

	if gap<maingap:
		maingap=gap
		count=i+1	

print(count)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
typedef long long int lint;
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> p(n), q(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i];
        p[i]--;
        q[p[i]] = i;
    }
    int temp = 1;
    int l = 1;
    for (int i = 0; i < n - 1; i++) {
        if (q[i] < q[i + 1]) {
            temp++;
            l = max(l, temp);
        } else {
            temp = 1;
        }
    }
    cout << n - l << endl;
}

Measured memory_bytes: 1920
#include<iostream>
#include <bits/stdc++.h>
#include<stdio.h>
#include <stdlib.h>
#include<string>
#include<queue>
#include<algorithm>
#include<math.h>
using namespace std;

int main(){
	priority_queue<unsigned long long int> q;
	unsigned long long int N,ren=1;
	unsigned long long int kiroku=0;
	unsigned long long int tate[2];
	unsigned long long int flag=0;
	cin>>N;
	for(int i=0;i<N;i++){
		int a;
		cin>>a;
		q.push(a);
	}
	while(!q.empty()){
		if(kiroku==q.top()){
			ren++;
		}else{
			ren=1;
		}
		kiroku=q.top();
		if(ren%2==0){
			tate[flag]=q.top();
			flag++;
		}
		if(flag==2){
			break;
		}
		q.pop();
	}
	if(flag!=2){
		cout<<"0"<<endl;
		return 0;
	}
	cout<<tate[0]*tate[1]<<endl;
}


Measured memory_bytes: 1400
#include <iostream>
#include<vector>
#include <iomanip>
using namespace std;

int main() {
	int n;cin>>n;
	vector<double> a(n);
	double den=0;
	for(int i=0;i<n;i++){
		cin>>a[i];
		den+=1/a[i];
	}
	cout << setprecision(15) <<1/den<<endl;

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mod 1000000007

int Max(int x, int y)
{
    return (((y-x)>>(32-1))&(x^y))^y;
}

int Min(int x, int y)
{
    return (((y-x)>>(32-1))&(x^y))^x;
}


int f(int a, int b, int m)
{
    if(a>b)
        return 0;
    if(a==b)
    {
        if(a%m==0)
            return 1;
        return 0;
    }
    if(a%m==0)
        return (b/m)-(a/m)+1;
    return (b/m)-(a/m);
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //Initialize variables while declaring them
    // int n, l, diff=100000000, sum=0;
    // cin>>n>>l;
    // vector<int> v;
    // for(int i=0; i<n; i++)
    // {
    //     v.pb(l+i);
    //     sum+=v.back();
    //     // cout<<v.back()<<" ";
    // }
    // for(int i=0; i<n; i++)
    //     if(abs(sum-(sum-v[i]))<diff)
    //         diff=abs(sum-abs(sum-v[i]));
    // // cout<<sum-diff;
    int a, b, c, d;
    cin>>a>>b>>c>>d;
    int sum=b-a+1;
    sum-=f(a, b, c);
    sum-=f(a, b, d);
    sum+=f(a, b, ((c*d)/__gcd(c, d)));
    cout<<sum;
    // cout<<f(a, b, c)<<endl<<f(a, b, d)<<endl<<f(a, b, ((c*d)/__gcd(c, d)));

    return 0;
}

Measured memory_bytes: 256
#ifdef _DEBUG
#include "MyLib.h"
#else
#define main_A main
#include "bits/stdc++.h" 
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LONG_MAX/2)
const int MGN = 8;
const int ARY_SZ_MAX = 10000000;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>;
// functions
ll gcd(ll a, ll b) {
    if (b == 0) return a;
    return gcd(b, a%b);
}

ll lcm(ll a, ll b) {
    ll g = gcd(a, b);
    return a / g * b;
}
#endif


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

    int N, M; cin >> N >> M;
    string S, T;  cin >> S >> T;
    
    ll L = lcm(N, M);

    queue<pii> a, b;
    int i = 1, j = 1;
    while(i<=N){
        a.push(pii(i-1,j-1));
        i++;
        j += L / N;
    }
    i = 1, j = 1;
    while(i<=M){
        b.push(pii(i-1, j-1));
        i++;
        j += L / M;
    }

    bool ok = true;
    while(!a.empty() && !b.empty()) {
        pii pa = a.front();
        pii pb = b.front();
        if (pa.second == pb.second) {
            if (S[pa.first] != T[pb.first]) {
                ok = false;
                break;
            } else {
                a.pop();
                b.pop();
            }
        } else if (pa.second < pb.second) {
            a.pop();
        } else {
            b.pop();
        }
    }

    ll ans = ok ? L : -1;
    cout << ans << endl;

    return 0;
}

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

Measured memory_bytes: 1852
N, M = map(int, input().split())

m10000 = -1
m5000 = -1
m1000 = -1
  
for a in range(N+1):
  for b in range(N+1-a):
    c = abs(N - a - b)
    X = 10000*a + 5000*b + 1000*c
    
    if X == M:
      m10000 = a
      m5000 = b
      m1000 = c

print(m10000, " ", m5000, " ", m1000)

Measured memory_bytes: 40812
# coding=utf-8
from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heappushpop, heapify
import copy
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


def lcm(a, b): return a * b / gcd(a, b)

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


n = I()
ans = 0
for a in range(1, n):
    ans += (n-1)//a

print(ans)


Measured memory_bytes: 68128
#include<iostream>
#include<stdio.h>
#include<vector>
#include<math.h>

using namespace std;

int main(){
	int ret=0;
	int sum = 0;

	while (scanf("%d", &ret) != EOF){

		for (int i = 1; i*ret <= 600-ret ;i++){
			sum += pow(i*ret,2) * ret;
		}

		cout << sum << endl;

		sum = 0;
	}

	return 0;
}

Measured memory_bytes: 1204
//Author: gkashish

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

#define mod 1000000007
#define x first
#define y second


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

    int n;
    cin>>n;
    string str;
    cin>>str;
    if(n&1){
        cout<<"No";
        return 0;
    }
    int k = n/2;
    for(int i=0;i<n/2;i++){
        if(str[i]!=str[k++]){
            cout<<"No";
            return 0;
        }
    }
    cout<<"Yes";
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 2e5 + 5;

char s[N];
int suf[N],cnt[N];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n,p;cin>>n>>p>>s+1;
	int base=1;
	ll ans=0;
	if(10%p==0){
		for(int i=1;i<=n;i++){
			if((s[i]-'0')%p==0) ans+=i;
		}
	}else{
		cnt[0]++;
		for(int i=n;i>=1;i--){
			int j=s[i]-'0';
			suf[i]=(suf[i+1]+j*base)%p;
			ans+=cnt[suf[i]];
			cnt[suf[i]]++;
			base=base*10%p;
		}
	}
	cout<<ans<<'\n';
	return 0;
}

Measured memory_bytes: 1280
from collections import deque
n = int(input())
graph = [[[] for _ in range(n+1)] for _ in range(n+1)]
indeg = [[0] * (n+1) for _ in range(n+1)]
for i in range(1, n+1):
    a = tuple(map(int, input().split()))
    for j, v in enumerate(a):
        if j == n-2:
            continue
        tmp = (min(i, a[j+1]), max(i, a[j+1]))
        indeg[tmp[0]][tmp[1]] += 1
        if i < v:
            graph[i][v].append(tmp)
        else:
            graph[v][i].append(tmp)

cnt = n * (n-1)//2
q = deque([])
for i in range(1, n+1):
    for j in range(i+1, n+1):
        if indeg[i][j] == 0:
            q.append((i, j, 1))
            cnt -= 1

ans = -1
while q:
    x, y, day = q.popleft()
    # print(x, y, day)
    ans = max(ans, day)
    for p, r in graph[x][y]:
        if indeg[p][r] == 0:
            continue
        indeg[p][r] -= 1
        if indeg[p][r] == 0:
            q.append((p, r, day+1))
            cnt -= 1

if cnt == 0:
    print(ans)
else:
    print(-1)

Measured memory_bytes: 181220
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define yes "Yes\n"
#define no "No\n"
int m,n;
//int i,j,k,l;
//int a,b,c,d,e,f,g;
//int sum,total;
//long long int ;
//float ;
//double ;
//char a[101],b[101],s[101],t[101],u[101];
int main(void){
    scanf("%d %d",&n,&m);
    if (n<=m)
    {
        printf(yes);
    } else
    {
        printf(no);
    }
    return 0;
}

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

int main() {
    string S;
    int Q;
    int flip = 0;
    string head = "";
    cin >> S >> Q;

    for (int i = 0; i < Q; ++i) {
        int type;
        cin >> type;
        if (type == 1) {
            flip += 1;
        } else {
            int f;
            string c;
            cin >> f >> c;
            if (f == 1 && flip % 2 == 0) {
                // S = c + S;
                head = head + c;
            } else if (f == 1 && flip % 2 != 0) {
                S = S + c;
            } else if (f != 1 && flip % 2 == 0) {
                S = S + c;
            } else {
                // S = c + S;
                head = head + c;
            }
        }
    }

    if (flip % 2 == 0) {
        reverse(head.begin(), head.end());
        S = head + S;
    } else {
        reverse(S.begin(), S.end());
        S = S + head;
    }
    cout << S << endl;
}

Measured memory_bytes: 1744
#include<stdio.h>
int main(void)
{
  int n,m,c,a[21][21],b[21],cnt=0,ans=0;
  scanf("%d%d%d",&n,&m,&c);
  for(int i=0;i<m;i++){
    scanf("%d",&b[i]);
  }
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      scanf("%d",&a[i][j]);
      cnt+=a[i][j]*b[j];
    }
    if(cnt+c>0){
      ans++;
    }
    cnt=0;
  }
  printf("%d",ans);
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define mk make_pair
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
int main(){
    ll n;
    while(cin>>n){
        ll ans=0, tmp;
        for(ll i=1; 1; ++i){
            tmp=(n-i)/i;
            if(tmp<=i){
                break;
            }
            if((n-i)%i==0){
                ans+=tmp;
            }
        }
        cout<<ans<<endl;
    }
  return 0;
}




Measured memory_bytes: 256
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner scn  = new Scanner(System.in);
		int n = scn.nextInt();
		int[] arr = new int[n];
		for(int i=0;i<n;i++)
			arr[i] = scn.nextInt();
		long ans = 0;
		for(int i=1;i<n;i++)
		{
			if(arr[i]<arr[i-1])
				{
					ans += (arr[i-1]-arr[i]);
					arr[i] = arr[i-1];
				}
		}
		System.out.println(ans);
		
	}
}


Measured memory_bytes: 60324
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
int n,a[N];
int main() {
  ios::sync_with_stdio(false);
  cin>>n;int s=0;
  for(int i=1;i<=n;i++)cin>>a[i],s^=a[i];
  //b[i]^a[i] =  s ^ a[i]
  for(int i=1;i<=n;i++){
  	cout<<(s^a[i])<<' ';
  }
 	return 0;
}

Measured memory_bytes: 4436
"""    Arnab Chanda    """

from collections import defaultdict, deque
from itertools import permutations
from sys import stdin,stdout
from bisect import bisect_left, bisect_right
from copy import deepcopy
import heapq

int_input=lambda : int(stdin.readline())
string_input=lambda : stdin.readline().split()
multi_int_input =lambda : map(int, stdin.readline().split())
multi_input = lambda : stdin.readline().split()
list_input=lambda : list(map(int,stdin.readline().split()))
string_list_input=lambda: list(string_input())
MOD = pow(10,9)+7

n, k = multi_int_input()

prices = list_input()

prices.sort()

s = 0
for i in range(k):
    s+=prices[i]

print(s)

Measured memory_bytes: 9680
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn];
map<int,int>maps;
map<int,int>::iterator it;
int n,m;
int ac = 0,wa = 0;
int main(void) {
    void solve();
    cin >> n >> m;
    ac = wa = 0;
    solve();
    return 0;
}
void solve() {
    if(m == 0) {
        cout << 0 << " " << 0 << endl;
        return ;
    }
    int num;
    string vis;
    for(int i = 1; i <= m; i ++) {
        cin >> num >> vis;
        if(maps[num] == -1) continue;
        if(vis == "AC") {
            wa += maps[num];
            ac += 1;
            maps[num] = -1;
            continue;
        }
        maps[num] ++;
    }
    maps.clear();
    cout << ac << " " << wa << endl;
    return ;
}

Measured memory_bytes: 4992
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include<iomanip>

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);i++)
#define all(x) (x).begin(),(x).end()

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

typedef long long ll;

using namespace std;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin>>n;
  vector<int>a(n);
  rep(i,n)cin>>a[i];
  int cnt=1<<30;
  sort(all(a));
  vector<pair<int,int>>as;
  int t=a[0],cn=0;
  rep(i,n)
  {
    if(t==a[i])
    {
      cn++;
    }
    else
    {
      as.push_back({t,cn});
      cn=1;
      t=a[i];
    }
  }
  as.push_back({t,cn});
  int res=0;
  int l=as.size();
  for(int i=l-1;i>=0;i--)
  {
    if(as[i].second==0)continue;
    while(cnt>2*as[i].first)cnt>>=1;
    int  f=lower_bound(all(as),make_pair(cnt-as[i].first,1))-as.begin();
    if(as[f].first==cnt-as[i].first)
    {
      if(i==f)
      {
        res+=as[f].second/2;
        as[f].second=as[f].second&1;
      }
      else
      {
        int tmp=min(as[i].second,as[f].second);
        res+=tmp;
        as[i].second-=tmp;
        as[f].second-=tmp;
      }
    }
  }
  cout<<res<<endl;
}


Measured memory_bytes: 3188
using System;
using System.Collections.Generic;
using System.Linq;
using System.Linq.Expressions;
using System.IO;
using System.Text;
using System.Diagnostics;

class Program
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        int[] a = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        Dictionary<int, int> map = new Dictionary<int, int>();

        for (int i = -1; i < 100002; i++)
        {
            map[i] = 0;
        }

        for (int i = 0; i < n; i++)
        {
            if (map.ContainsKey(a[i])) {
                map[a[i]]++;
            }
            else
            {
                map[a[i]] = 1;
            }
        }

        long ans = map.Values.Max();

        for(int i = 0; i < n; i++)
        {
            ans = Math.Max(ans, map[i - 1] + map[i] + map[i + 1]);
        }

        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 25440
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <queue>

using namespace std;

#define int long long

vector<int> tmp;

signed main() {
	int a, b, c, d;
	cin >> a >> b >> c >> d;

	cout << max(a*b, c*d) << endl;

}


Measured memory_bytes: 764
n,x,y = map(int,input().split())
ans = {}
s = (y-x+1)//2
s = x+s
for i in range(1,n):
    for j in range(i+1,n+1):
        if i <= s:
            dist = min(j-i,abs(i-x)+abs(j-y)+1)
        else:
            dist = j-i
        if dist in ans.keys():
            ans[dist] += 1
        else:
            ans[dist] = 1
for k in range(1,n):
    if k in ans.keys():
        print(ans[k])
    else:
        print(0)

Measured memory_bytes: 3572
n,m = map(int,input().split())
S = [list(map(int,input().split()))[1:] for _ in range(m)]
P = list(map(int,input().split()))
A = int("1"*n,2)
cnt = 0
for i in range(A+1):
    a = bin(i)[2:].zfill(n)
    l = list(map(int,list(a)))
    for j in range(m):
        cnt1 = 1
        b = 0
        for s in S[j]:
            b += l[s-1]
        if b%2 != P[j]:
            cnt1 = 0
            break
    cnt += cnt1
print(cnt)


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

const int maxn=1e6+7;

int prime[maxn],flag=0,a[100];

void getprime(){
    memset(prime,0,sizeof(prime));
    for(int i=2;i<=maxn;i++){
        if(!prime[i])  prime[flag++]=i;
        for(int j=0;j<flag;j++){
            if(i*prime[j]>=maxn) break;
            prime[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        }
    }
}

int main (){
    getprime();
    int n,cnt=0;
    cin>>n;
    for(int i=0;i<flag&&cnt<n;i++) if(prime[i]%5==1) a[cnt++]=prime[i];
    for(int i=0;i<n;i++) printf(i==n-1?"%d\n":"%d ",a[i]);
    return 0;
}


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

int main() {
  string s;
  cin >> s;
  
  int ans = 0;
  for(int i=0; i<4; i++) {
    if(s[i]=='2') ans++;
  }
  cout << ans << endl;
  return 0;
}

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

public class Main {
	static int gcd (int a, int b) {
	    return b == 0 ? a : gcd (b, a % b);
	}
	
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		System.out.println((2*n)/gcd(2,n));
	}
}

Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef long int li;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<float, float> ff;
typedef pair<double, double> dd;
typedef unsigned int ui;
typedef vector<ii> vii;
typedef vector<ff> vff;
typedef set<int> si;
typedef set<lli> slli;
typedef vector<lli> vlli;
typedef long long ll;
typedef long long ll;
typedef vector<ll> vll;
typedef unsigned long long int ulli;
#define MOD 1000000007
#define INF (unsigned)(~0)>>1
typedef pair<int, ii> iii;
void arr_int(int* given_arr, int n){
  for(int i=0;i<n;i++)
    scanf("%d", &given_arr[i]);
}
void solve();
int main(int argc, char const *argv[]){
  solve();
  return 0;
}
void solve(){
  string s;
  cin>>s;
  if(s[0] == s[1] && s[1] == s[2])
    printf("%s\n", "No");
  else
    printf("%s\n", "Yes");
}


Measured memory_bytes: 256
void main() {
	auto ip = readAs!(int[]), H = ip[0], W = ip[1];
	auto c = readMatrix!string(H, W);
	foreach(hi, hv; c) {
		foreach(wi, wv; hv) {
			if(wv == "snuke") {
				writefln("%s%d", ('A'+wi).to!char, hi+1);
			}
		}
	}
}

// ===================================

import std.stdio;
import std.string;
import std.functional;
import std.algorithm;
import std.range;
import std.traits;
import std.math;
import std.container;
import std.bigint;
import std.numeric;
import std.conv;
import std.typecons;
import std.uni;
import std.ascii;
import std.bitmanip;
import core.bitop;

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
//size_t f = string::npos
//make pair, tuple

int main(){
      int n,m;cin >> n >> m;
      int arr[n + 5];
      for(int i = 0;i < n;i++)arr[i] = 0;
      for(int i = 0;i < m;i++){
            int t,t2;cin >> t >> t2;
            arr[t]++;
            arr[t2]++;
      }
      for(int i = 0;i < n;i++){
            cout << arr[i + 1] << "\n";
      }
}

Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include<iostream>
#include<algorithm>//next_permutation
#include<complex>
#include<math.h>
using namespace std;
#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, j, n) for (int i = j; i < (int)(n); i++)

int main() {
	int N;
	cin >> N;
	vector<int> a(N - 1);
	vector<int>b(N); // 直属の上司
	rep(i, N - 1) {
		cin >> a.at(i);
	}
	rep(i, N) {
		b.at(i) = 0;
	}
	reverse(a.begin(), a.end());
	rep(i, N - 1) {
		if (a.at(i) != N - i) {
			b.at(a.at(i) - 1) += 1;
        }
	}
	rep(i, N) {
		cout << b.at(i) << endl;
	}
}


Measured memory_bytes: 4840
#include <memory.h>

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>

using namespace std;

#define mod 1000000007

int main() {
	int k;
	cin >> k;
	int res[15][10] = {};
	// res[i][j] : 長さがiで、10^(i-1)の桁の値が
	// jであるようなルンルン数の総数
	for (int i = 0; i < 10; i++) {
		res[1][i] = 1;
	}
	for (int i = 2; i < 15; i++) {
		res[i][0] = res[i - 1][0] + res[i - 1][1];
		for (int j = 1; j < 9; j++) {
			res[i][j] = res[i - 1][j] + res[i - 1][j - 1] + res[i - 1][j + 1];
		}
		res[i][9] = res[i - 1][9] + res[i - 1][8];
	}
	long long int sumres[15][10] = {};
	for (int i = 1; i < 15; i++) {
		sumres[i][0] = sumres[i - 1][9];
		for (int j = 1; j < 10; j++) {
			sumres[i][j] = sumres[i][j - 1] + res[i][j];
		}
	}
	long long int ans = 0;
	for (int i = 14; i >= 1; i--) {
		if (ans == 0) {
			for (int j = 9; j >= 1; j--) {
				// cout << k << " " << i << " " << j << " " << sumres[i][j]
				//      << endl;
				if (k > sumres[i][j - 1]) {
					k -= sumres[i][j - 1];
					ans = (ans * 10) + j;
					break;
				} else if (k == sumres[i][j]) {
					k -= sumres[i][j];
					ans = (ans * 10) + j;
					break;
				}
			}
		} else {
			int tmp = ans % 10;
			int tmpsum = 0;
			for (int j = max(0, tmp - 1); j <= min(9, tmp + 1); j++) {
				// cout << k << " " << i << " " << j << " " << sumres[i][j]
				//      << endl;
				tmpsum += res[i][j];
				if (tmpsum >= k) {
					tmpsum -= res[i][j];
					k -= tmpsum;
					ans = (ans * 10) + j;
					break;
				}
			}
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for(int i=0;i<n;i++)
#define why(n,x) int n;while(cin >>n,n!=x)
#define iFOR(i,x,n)for(int i=x;i<n;i++)
#define fin <<'\n'
#define __ <<" "<<
#define ___ <<" "
#define bash push_back
#define ALL(x) x.begin(),x.end()
#define SWAP(a,b) ((a != b) && (a += b,b = a - b,a -= b))
//#define int long long
typedef long long ll;
typedef pair < int , int >  pii;
typedef vector < int > vit;
typedef map < string , int > mstit;
typedef vector < pii > vpi ;
typedef greater < pii > gpi;
typedef priority_queue < pii , vpi , gpi > dijk ;
static const signed int INF = 0x3f3f3f3f;
static const signed long long LINF = 0x3f3f3f3f3f3f3f3fLL;
static const signed int SMOD = 1000000007;
static const signed int NMOD = 1000000009;
static const signed int dx[]={1,0,-1,0,1,1,-1,-1};
static const signed int dy[]={0,-1,0,1,-1,1,-1,1};

bool inside(int x,int y,int w,int h){return (x>=0 && y>=0 && x<w && y<h);}
template<class T>T abs(T &x){return x<0 ? -x : x;}
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
int qp(int a,ll b,int mo){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}

int n, W;
vector<int> w, v;
ll dp[105][101005];

inline void solve(){

    cin >> n >> W;
    w.resize(n);
    v.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> w[i] >> v[i];
    }

    for(int i = 0; i <= 100100; i++)
        dp[0][i] = LINF;
    dp[0][0] = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j <= 100100; j++) {
            dp[i+1][j] = dp[i][j];
            if(j-v[i] >= 0)
                chmin(dp[i+1][j], dp[i][j-v[i]]+w[i]);
        }
    }

    int ans = 0;
    for(int i = 0; i <= 100100; i++) {
        if(dp[n][i] <= W) ans = i;
    }
    
    
    cout << ans << endl;
    
}
struct xyz{ xyz(){ cin.tie(0), ios::sync_with_stdio(false); cout <<fixed<<setprecision(12);};}xyzzy;signed main(){solve();return 0;}


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

const int N=5010,mod=1000000007;
typedef long long ll;
int ksm(ll a,int b,int c=1){
	for(;b;b/=2,a=a*a%mod)
		if(b&1)c=c*a%mod;
	return c;
}
int jc[N],jc2[N];
void Init(){
	jc[0]=jc2[0]=1;
	for(int i=1;i<N;++i)jc[i]=(ll)jc[i-1]*i%mod,jc2[i]=ksm(i,mod-2,jc2[i-1]);
}
int C(int n,int k){return (ll)jc[n]*jc2[k]%mod*jc2[n-k]%mod;}
int n,dp[2][N],sz[N],rt,T,ans;
vector<int>g[N];

void dfs(int x,int fa=-1){
	int mx=0;sz[x]=1;
	for(int i:g[x])if(i!=fa){
		dfs(i,x);sz[x]+=sz[i];
		mx=max(mx,sz[i]);
	}
	mx=max(mx,n-sz[x]);
	if(!rt&&mx*2<=n)rt=x;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;Init();
	for(int i=1;i<n;++i){
		int x,y;cin>>x>>y;
		g[x].push_back(y);g[y].push_back(x);
	}
	dfs(1);dfs(rt);
	dp[0][0]=1;
	int sum=0;
	for(int i:g[rt]){
		T^=1;memset(dp[T],0,sizeof dp[T]);
		for(int j=0;j<=sum;++j)if(dp[!T][j])
			for(int k=0;k<=sz[i];++k)
				dp[T][j+k]=(dp[T][j+k]+(ll)dp[!T][j]*C(sz[i],k)%mod*C(sz[i],k)%mod*jc[k])%mod;
		sum+=sz[i];
	}
	for(int i=0;i<=n;++i){
		int tmp=(ll)dp[T][i]*jc[n-i]%mod;
		if(i&1)ans=(ans-tmp+mod)%mod;
		else ans=(ans+tmp)%mod;
	}
	cout<<ans<<'\n';
	return 0;
}


Measured memory_bytes: 896
//
//  second.cpp
//  CoderTest
//
//  Created by yuya on 2019/07/25.
//  Copyright © 2019 yuya. All rights reserved.
//

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair <int,int> P;
#define ALL(x) (x).begin(), (x).end()
#define INF 1000000


int main()
{
    int mod = 100000;
    vector<vector<int>> ch(mod);
    int N;
    cin >> N;
    vector<int> A(N+1);
    int a;
    int noflag = 0;
    
    for (int i=0; i<N; i++) {
        cin >> A[i];
        a = A[i] % mod;
        for (int j=0; j<ch[a].size(); j++) {
            if(ch[a][j] == A[i]){
                noflag = 1;
            }
        }
        if(noflag) break;
        ch[a].push_back(A[i]);
        
    }
    
    if(noflag){
        cout << "NO" << endl;
    } else {
        cout << "YES" << endl;
    }
    
    
    
    return 0;
}


Measured memory_bytes: 6144
#include<bits/stdc++.h>
using namespace std;
void dfs(vector<vector<int>>& adj,vector<int>& visit,vector<int>& top,int i){
    visit[i]=1;
    for(auto x:adj[i]){
        if(visit[x]==0)
        dfs(adj,visit,top,x);
    }
    top.push_back(i);
}
int main(){
    int n,m; cin>>n>>m;
    vector<vector<int>>adj(n);
    for(int j=0;j<m;j++){
        int a,b; cin>>a>>b;
        adj[a-1].push_back(b-1);
    }
    vector<int>top;
    vector<int>dp(n,0);
    vector<int>visit(n);
    for(int i=0;i<n;i++){
        if(visit[i]==0){
            dfs(adj,visit,top,i);
        }
    }

    for(int i=0;i<n;i++){
        int val=-1;
        for(auto x:adj[top[i]]){
            val=max(val,dp[x]);
        }
        dp[top[i]]=val+1;
    }
    //for(auto x: top ) cout<<x<<" "; cout<<endl;
    //for(auto x: dp ) cout<<x<<" "; cout<<endl;
    cout<<*max_element(dp.begin(),dp.end())<<endl;
    return 0;
}

Measured memory_bytes: 9852
class Dice

    attr_accessor :dice_pos_1,:dice_pos_2,:dice_pos_3,:dice_pos_4,:dice_pos_5,:dice_pos_6

    def initialize(dice_num:[])
        @dice_pos_1 = dice_num[0]
        @dice_pos_2 = dice_num[1]
        @dice_pos_3 = dice_num[2]
        @dice_pos_4 = dice_num[3]
        @dice_pos_5 = dice_num[4]
        @dice_pos_6 = dice_num[5]
    end
    def parse_spin(spin_directions:[])
        spin_directions.each do |spin|
            if spin == "N"
                turn_north()
            elsif spin == "S"
                turn_south()
            elsif spin == "W"
                turn_west()
            elsif spin == "E"
                turn_east()
            end
        end
        return self
    end
    def turn_north
        @dice_pos_1,@dice_pos_2,@dice_pos_5,@dice_pos_6 = @dice_pos_2,@dice_pos_6,@dice_pos_1,@dice_pos_5
        return self
    end
    def turn_south
        @dice_pos_1,@dice_pos_2,@dice_pos_5,@dice_pos_6 = @dice_pos_5,@dice_pos_1,@dice_pos_6,@dice_pos_2
        return self
    end
    def turn_west
        @dice_pos_1,@dice_pos_3,@dice_pos_4,@dice_pos_6 = @dice_pos_3,@dice_pos_6,@dice_pos_1,@dice_pos_4
        return self
    end
    def turn_east
        @dice_pos_1,@dice_pos_3,@dice_pos_4,@dice_pos_6 = @dice_pos_4,@dice_pos_1,@dice_pos_6,@dice_pos_3
        return self
    end
end

taregt_dice = Dice.new(dice_num:gets.split.map(&:to_i))
dices = [Dice.new(dice_num:gets.split.map(&:to_i))]
same = false
6.times do
    dices.each do |dice|
        if dice.dice_pos_1 == taregt_dice.dice_pos_1 && dice.dice_pos_2 == taregt_dice.dice_pos_2 && dice.dice_pos_3 == taregt_dice.dice_pos_3 && dice.dice_pos_4 == taregt_dice.dice_pos_4 && dice.dice_pos_5 == taregt_dice.dice_pos_5 && dice.dice_pos_6 == taregt_dice.dice_pos_6
            same = true
        end
    end
    new_dices = []
    dices.each do |dice|
        new_dices.push(dice.clone.turn_north)
        new_dices.push(dice.clone.turn_south)
        new_dices.push(dice.clone.turn_east)
        new_dices.push(dice.clone.turn_west)
    end
    dices = new_dices
end
if same
    puts "Yes"
else
    puts "No"
end


Measured memory_bytes: 7200
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,M = inpl()
if N == M:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 4324
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> lpair;
const ll MOD = 1e9 + 7;
#define rep(i,m,n) for(ll i = (m); i < (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define print2(x,y) cout << (x) << " " << (y) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " ";} cout<<endl;
#define INF (1e18)
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N,M;
    cin >> N >> M;
    ll A[100010];
    rep(i,0,N){
        cin >> A[i];
        A[i]--;
    }
    map<ll, ll> mp;
    rep(i,0,N-1){
        mp[A[i+1]] += (A[i+1] - A[i] + M) % M - 1;
    }
    ll sum[100010] = {};
    rep(i,0,N-1){
        if(A[i] < A[i+1]){
            sum[A[i]+1]++;
            sum[A[i+1]]--;
        }else{
            sum[A[i]+1]++;
            sum[0]++;
            sum[A[i+1]]--;
        }
    }
    rep(i,0,M+1) sum[i+1] += sum[i];
    ll val = 0;
    rep(i,0,N-1){
        val += min((A[i+1] - A[i] + M) % M, 1 + (A[i+1] + M) % M);
    }
    ll ans = INF;
    rep(i,0,M){
        ans = min(ans, val);
        val -= sum[i];
        val += mp[i];
    }
    print(ans);
}

Measured memory_bytes: 8064
#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
using namespace std;

typedef long long ll;
#define rep(i, n) for(int i = 0; i < n; i++)

int main(){
    int K;
    cin >> K;
    int limit = pow(10, 7);
    int val = 0;
    int v = 1;
    rep(i, limit){
        if(i > 0){
            v *= 10;
            v = v % K;
        }

        val = (7 * v + val) % K;
        if(val == 0){
            cout << i+1 << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}

Measured memory_bytes: 3624