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

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvvi = vector<vector<vector<int>>>;
using mii = map<int, int>;
using msi = map<string, int>;
using pii = pair<int, int>;

msi a{{"SUN",7},{"MON",6},{"TUE",5},{"WED",4},{"THU",3},{"FRI",2},{"SAT",1}}; // mapの宣言

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    cout << a[s] <<endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
int main()
{
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);

	int A,B,C;
	std::cin >> A;
	std::cin >> B;
	std::cin >> C;
	for(int i=1; i<B; i++)
	{
		int modAB = (A*i) % B;
		bool result = modAB==C;
		if(result){
			std::cout << "YES" << std::endl;
			return 0;
		}
	}

	std::cout << "NO" << std::endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <queue>
#include <cmath>
using namespace std;


int main() {
    int a, b;
    cin >> a >> b;
    int res = 0;
    for (int i = 1; i <= a; i++) {
        if (i < a) res++;
        else if (i == a && i <= b) res++;
    }
    cout << res << endl;
}


Measured memory_bytes: 3576
N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
lr = [tuple(map(int, input().split())) for _ in range(Q)]
for i in range(N):
    t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for l, r in lr:
    print(t[r-1] - t[l-1])

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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

void Main() {
    ll N, K;
    cin >> N >> K;
    ll ans = 0;
    while (N > 0) {
        N /= K;
        ans++;
    }
    cout << ans << '\n';
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}


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

int main(){
    int n;
    cin >> n;
    vector<int>a(n);
    int maxv, maxv2;
    int index_max;

    for (int tsumugi = 0; tsumugi < n; tsumugi++){
        cin >> a[tsumugi];
    }
    
    for (int matsuri = 0; matsuri < n; matsuri++){
        if (a[matsuri] > maxv){
            maxv = a[matsuri];
            index_max = matsuri;
        }
    }

    a[index_max] = 0;

    for (int kaori = 0; kaori < n; kaori++){
        if (a[kaori] > maxv2){
            maxv2 = a[kaori];
        }
    }

    for (int reika = 0; reika < n; reika++){
        if (reika != index_max)
            cout << maxv << endl;
        else
            cout << maxv2 << endl;
    }

    return 0;
}

Measured memory_bytes: 2432
import numpy as np
Nn, Kk, Qq = input().split()
N, K, Q = int(Nn), int(Kk), int(Qq)
a = []
for q in range(Q):
    a.append(int(input()))
result = np.ones(N) * (K - Q)
for i in a:
    result[i-1] += 1
result = result > 0
for r in result:
    if r:
        print("Yes")
    else:
        print("No")

Measured memory_bytes: 17832
#import<iostream>
main(){int n,c,i,a[1<<17]={};for(std::cin>>n;n--;){std::cin>>i;if(!a[i]++){++c;a[i]++;}}for(i=1<<17;i--;)n^=a[i]&1;std::cout<<(n&1?c:c-1);}

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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int n,k; string s; cin>>n>>k>>s;
	vector<int>a(1,0);
	if(s.front()=='0')a.emplace_back(0);
	for(int i=0;i<s.size();){
		int cnt=0; char c=s.at(i);
		while(i<s.size()&&s.at(i)==c)++i,++cnt;
		a.emplace_back(cnt);
	}
	for(int i=1;i<a.size();++i)a.at(i)+=a.at(i-1);
	if(s.back()=='0')a.emplace_back(a.back());
	int ans=0;
	for(int i=min(k*2+1,(int)a.size()-1),base=i;i<a.size();i+=2){
		ans=max(ans,a.at(i)-a.at(i-base));
	}
	cout<<ans<<"\n"s;
}

Measured memory_bytes: 1020
import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int k = Integer.parseInt(st.nextToken());
        int t = Integer.parseInt(st.nextToken());
        int array[] = new int[t + 1];
        st  = new StringTokenizer(br.readLine());
        for(int i = 1;i <= t;i++){
            array[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(array);
        int start = 1;
        int ans[] = new int[k + 1];
        for(int i = t ;i >= 1;i--){
            for(int j = 1;j <= array[i];j++){
                ans[start] = i;
                start += 2;
                if(start > k)start = 2;
            }
        }
        int days = 0;
        for(int i = 2;i <= k;i++){
            if(ans[i] == ans[i - 1])++days;
        }
        if((k & 1) == 0 && array[t] > k/2 && array[t] != k)--days;
        System.out.print(days);
    }
}

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

int main() {
	int n, m; scanf("%d%d", &n, &m);

	map<int, char> mp;
	map<int, int> cnt;

	int ans1 = 0, ans2 = 0;
	for (int i = 0; i < m; i++) {
		int p; scanf("%d", &p);
		char c; scanf(" %c%*c", &c);

		if (c == 'A') {
			if (mp[p] == 'A') continue;

			mp[p] = 'A';
			ans1++;
			ans2 += cnt[p];
		} else cnt[p]++;
	}

	printf("%d %d\n", ans1, ans2);

}

Measured memory_bytes: 9600
#include<cstdio>
#define ull unsigned long long
int n;
ull sum;
int main()
{
	scanf("%d", &n);
	for(int i=1; i<=n; i++) 
	{
		int x;
		scanf("%d", &x), sum+=x;
	}
	if(sum&1) printf("NO\n");
	else printf("YES\n");
}

Measured memory_bytes: 128
N,M=map(int,input().split())
List=[0]*N
for i in range(M):
  a,b=map(int,input().split())
  List[a-1]+=1
  List[b-1]+=1

for i in range(N):
  if List[i]%2==1:
    print("NO")
    exit()
    
print("YES")

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

template<uint32_t N>
struct Sieve_of_Eratosthenes{
  using i32 = int32_t;
  std::array<i32,N+1> factor;
  Sieve_of_Eratosthenes(){
    factor.fill(0);
    for(i32 p=2;p<=N;++p){
      if(factor[p])continue;
      factor[p] = p;
      for(i32 x=p+p;x<=N;x+=p){
        if(factor[x])continue;
        factor[x] = p;
      }
    }
  }
  std::vector<i32> prime_factor(i32 x){
    std::vector<i32> pf;
    while(factor[x]){
      pf.push_back(factor[x]);
      x /= factor[x];
      while(factor[x]==pf.back())x/=factor[x];
    }
    return pf;
  }
};

signed main(){
  using namespace std;
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n;
  cin>>n;
  vector<int> a(n);
  for(auto& ai:a)cin>>ai;

  constexpr int a_max = 1e6;
  Sieve_of_Eratosthenes<a_max> ushi;

  map<int,int> mp;
  bool pairwise_coprime = true;
  for(auto const& ai:a){
    for(auto const& p:ushi.prime_factor(ai)){
      if(mp.count(p)){
        pairwise_coprime = false;
        break;
      }
      mp[p]++;
    }
  }
  
  if(pairwise_coprime){
    cout<<"pairwise coprime"<<endl;
    return 0;
  }

  bool setwise_coprime = accumulate(begin(a),end(a),0,[](auto a,auto b){return gcd(a,b);}) == 1;
  if(setwise_coprime){
    cout<<"setwise coprime"<<endl;
    return 0;
  }

  cout<<"not coprime"<<endl;


}

Measured memory_bytes: 14620
#include<iostream>

using namespace std;

int main() {
	long long n, res = 1;
	unsigned long long sum=6;
	
	cin >> n;

	res = n / 11 * 2;
	int r = n % 11;
	if (r == 0);
	else if (r <= 6)res += 1;
	else res += 2;

	cout << res << endl;

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
char dp[12][12];
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
void DFS(int x,int y){
	dp[y][x]='0';
	for(int i=0;i<4;i++){
		if(x+dx[i]>=0&&x+dx[i]<12&&y+dy[i]>=0&&y+dy[i]<12){
			if(dp[y+dy[i]][x+dx[i]]=='1')
			DFS(x+dx[i],y+dy[i]);
		}
	}
	return;
}
int main(){
	while(cin>>dp[0][0]){
		int ans=0;
	for(int i=0;i<12;i++)
		for(int j=0;j<12;j++)
			if(i+j!=0){cin>>dp[i][j];}
	for(int i=0;i<12;i++){
		for(int j=0;j<12;j++){
			if(dp[i][j]=='1'){
				ans++;
				DFS(j,i);
			}
		}
	}
	cout<<ans<<endl;
	}
	return 0;
}

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

int main(void) {
    int N;
    int sum = 0;
    int maxp = 0;
    cin >> N;

    vector<int> p(N);
    for(int i=0;i<N;i++) {
        cin >> p[i];
        sum += p[i];
        if(maxp <p[i]) {
            maxp = p[i];
        }
    }

    cout << sum - (maxp/2) << endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main() {

    int r,c,x[102][102]={0};
    cin>>r>>c;

    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            cin>>x[i][j];//入力
            x[i][c]+=x[i][j];//横列の合計
        }
    }

    for(int i=0;i<=c;i++){
        for(int j=0;j<r;j++){
            x[r][i]+=x[j][i];//縦列の合計
        }
    }

    for(int i=0;i<=r;i++){
        for(int j=0;j<=c;j++){
            if(j!=0)cout<<" ";
            cout<<x[i][j];//出力
        }cout<<endl;
    }

    return 0;
}


Measured memory_bytes: 3144
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<iostream>
#define LL long long
#define N 500
#define mmod 1000000007
using namespace std;
LL f[N],cnt[N],a[N][N][2],x,y,ans;
int n;
void solve1(LL x,LL y)
{
	for(int i=1;i<=x;i++)
	{
		ans=(ans+y/i)%mmod;
		if(y/i==0) break;
	}
	for(int i=1;i<=y;i++)
	{
		ans=(ans+x/i)%mmod;
		if(x/i==0) break;
	}
	ans=(ans-min(x,y))%mmod;
	ans=(ans+mmod)%mmod;
}
void solve(LL a,LL b,LL x,LL y)
{
	if(b>x || b+a>y) return;
	ans=(ans+(y-a)/b)%mmod;
}
int main()
{
	f[0]=f[1]=1;
	for(int i=2;;i++)
	{
		f[i]=f[i-1]+f[i-2];
		if(f[i]>1e18) {n=i;break;}
	}
	n-=2;
	cnt[1]=2;
	a[1][1][0]=1;a[1][1][1]=2;a[1][2][0]=1;a[1][2][1]=3;
	for(int i=1;i<n;i++)
		for(int j=1;j<=cnt[i];j++)
		{
			LL t=a[i][j][0]+a[i][j][1];
			while(t<=f[i+3])
			{
				a[i+1][++cnt[i+1]][0]=a[i][j][1];
				a[i+1][cnt[i+1]][1]=t;
				t+=a[i][j][1];
			}
		}
	int z;scanf("%d",&z);
	while(z--)
	{
		scanf("%lld%lld",&x,&y);
		if(x>y) swap(x,y);
		int k=1;
		for(int i=1;i<=n;i++) 
			if(f[i]<=x && f[i+1]<=y) k=i;
			else break;
		ans=0;
		printf("%d ",k);
		if(k==1) solve1(x,y);
		else for(int i=1;i<=cnt[k-1];i++) solve(a[k-1][i][0],a[k-1][i][1],x,y),solve(a[k-1][i][0],a[k-1][i][1],y,x);
		printf("%lld\n",ans);
	}
	return 0;
}

Measured memory_bytes: 4480
import sys
from collections import deque

N = int(input())
A = [deque([int(i) for i in input().split()]) for i in range(N)]

ans=0
empty = [deque() for i in range(N)]
pre_fight = set([i for i in range(N)])
record = set()

while True:
    for g in pre_fight:
        if A[g]!=deque():
            if g+1 == A[A[g][0]-1][0]:
                record.add(g)
                record.add(A[g][0]-1)
    if record==set():
        break
    else:
        for i in record:
            A[i].popleft()
    ans+=1
    pre_fight = record
    record = set()
    if A==empty:
        print(ans)
        sys.exit()

print(-1)

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

int main(){
    int A1,A2,A3;
    int all;
    cin >> A1 >> A2 >> A3;
    
    all = A1 + A2 + A3;
    if ( all >= 22 ){
        cout << "bust" << endl;
    } else {
        cout << "win" << endl;
    }
    
    
    return 0;
}


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

max_L = -1
min_R = 10**5 + 1
for _ in range(M):
    L, R = map(int, input().split())
    max_L = max(max_L, L)
    min_R = min(min_R, R)

print(max(min_R - max_L + 1, 0))


Measured memory_bytes: 45544
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
#define chmin(x,y) x = min(x,y)
using namespace std;
typedef long long ll;
const long long INF = 1LL << 60;
ll dp[110000]; //配列数は問題に応じて

int main() {
    int n;
    cin>>n;
    rep(i,110000) dp[i] = INF;
    dp[0]=0;
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j*=6){
            dp[i] = min(dp[i],dp[i-j]+1);
        }
        for(int k=1;k<=i;k*=9){
            dp[i] = min(dp[i],dp[i-k]+1);
        }
    }
                      
    cout<<dp[n]<<endl;
    
    return 0;
}


Measured memory_bytes: 1152
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>
#include <stdlib.h>
#include <stdio.h>
#include <functional>
#include <cfloat>
#include <math.h>
#include <numeric>
#include <string.h>
#include <sys/time.h>
#include <random>


#define fs first
#define sc second

using namespace std;

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

int ab(int x){
    if(x <= 0){
        x = -x;
    }
    return x;
}

unordered_map<int, int> cand[2][100];


int main(){
    int h, w;
    cin >> h >> w;
    int x[100][100];
    int a[100][100];
    int b[100][100];
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            cin >> a[i][j];
        }
    }
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            cin >> b[i][j];
        }
    }
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            x[i][j] = max(a[i][j], b[i][j]) - min(a[i][j], b[i][j]);
        }
    }

    int xs[100][100];
    xs[h-1][w-1] = x[h][w];
    for(int i = h-1; i >= 0; i--){
        for(int j = w-1; j >= 0; j--){
            if(i -1 >= 0){
                xs[i-1][j] = x[i-1][j] + xs[i][j];
            }
            if(j-1 >= 0){
                xs[i][j-1] = x[i][j-1] + xs[i][j];
            }
        }
    }

    cand[0][0][x[0][0]] = 1;
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            cand[(i+1) % 2][j].clear();
        }
        for(int j = 0; j < w; j++){
            for (auto sx: cand[i%2][j]) {
                if(sx.fs - xs[i][j] > 80){
                    continue;
                }
                if(i + 1 < h) {
                    cand[(i + 1) % 2][j][ab(sx.fs + x[i + 1][j])] = 1;
                    cand[(i + 1) % 2][j][ab(sx.fs - x[i + 1][j])] = 1;

                }
                if(j + 1 < w) {
                    cand[i % 2][j + 1][ab(sx.fs + x[i][j + 1])] = 1;
                    cand[i % 2][j + 1][ab(sx.fs - x[i][j + 1])] = 1;
                }
            }
        }
    }

    int res = INT32_MAX;
    for(auto sx: cand[(h-1) % 2][w-1]){
        res = min(res, sx.fs);
    }
    cout << res << endl;


    return 0;
}




Measured memory_bytes: 18816
#include <bits/stdc++.h>
 
using namespace std;
 
/*-------------------------------*/
#define FOR(i, a, b) for(int i = (a); i < (b); i++) 
#define RFOR(i, a, b) for(int i = (b) - 1; i >= (a); i--)
#define REP(i, n) for(int i = 0; i < (n); i++)
#define RREP(i, n) for(int i = (n) - 1; i >= 0; i--)
#define all(i) (i).begin(),(i).end()
#define pb push_back
#define mp make_pair 
 
typedef long long ll;
typedef pair<int, int> pint;
typedef vector<int> vi;
typedef vector<vector<int> > vii;
typedef vector<long long> llv;
typedef vector<pint> vpint;
/*-------------------------------*/
 
int main(void)
{
  int a = 0, b = 0, c;
  REP(i, 4){
    cin >> c;
    a += c;
  }
  REP(i, 4){
    cin >> c;
    b += c;
  }
  cout << max(a, b) << endl;
  
  return (0);
}

Measured memory_bytes: 3104
n = int(input())
li = [] # AとBのリスト
x = 0
 
for i in range(n):
    li.append(list(map(int,input().split())))
li.sort(key=lambda x: x[1]) # Bの締め切りの早いものでソート
 
for i in range(n):
    x += li[i][0]
    if x > li[i][1]:
        print("No") # 締め切りの早いものから終わらせていき、終わらなかったらNo
        exit()
 
print("Yes")

Measured memory_bytes: 53720
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(s,i, n) for (int i = (int)s; i < (int)(n); i++)
#define pb push_back
typedef long long ll;
  
int main(){
    string s;
    cin>>s;
    int l =s.length();
    bool check=true;
    rep(i,l){
        if(i%2==0){
            if(s[i]=='L')check=false;
        }else{
            if(s[i]=='R')check=false;
        }
    }
    string ans=check?"Yes":"No";
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <vector>
#define rep(i,n) for(int i = 0; i < n; i++)
using ll = long long;
using namespace std;
int main(){
  int n,k;
  cin >> n >> k;
  int ans = 0;
  rep(i,n){
    int x;
    cin >> x;
    ans += min(x, k - x);
  }
  cout << ans * 2 << endl;
  return 0;
}

Measured memory_bytes: 256
/*input
1
3 3
1 2 3
*/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll , ll> PLL;
typedef long double ld;

#define pb push_back
#define all(c) c.begin(),c.end()
#define allr(c) c.rbegin(),c.rend()
int mod = 1000000007;
#define PI 3.14159265
#define endl '\n'
#define debug(x) cout << #x << " = " << x << endl;
#define MAX 100001

template < typename T > T GCD(T a, T b)            { ll t; while(a) { t = a; a = b % a; b = t; } return b; }
template < typename T > string toString(T a)       { return to_string(a); }
template < typename T > void toInt(string s, T &x) { stringstream str(s); str >> x;}
inline int add(ll a, ll b) {a += b; if (a < 0) a += mod; return a;}
inline int sub(ll a, ll b) {a -= b; if (a < 0) a += mod; return a;}
inline int mul(ll a, ll b) {return (a * 1ll * b) % mod;}
inline int pwr(ll x, ll y) {
    int ans = 1 % mod;
    while (y) {
        if (y & 1) ans = mul(ans, x);
        x = mul(x, x);
        y >>= 1;
    }
    return ans;
}
inline int inv(int a) {return pwr(a, mod - 2);}

vector <int> adj[MAX];
set <int> s;
int mp[MAX];
ll dc;

struct DSU {
    int connected;
    int par[MAX], sz[MAX];
    DSU(int n) {
        for (int i = 1; i <= n; i++) {
            par[i] = i;
            sz[i] = 1;
        }
        connected = n;
    }
    int getPar(int k) {
        while (k != par[k]) {
            par[k] = par[par[k]];
            k = par[k];
        }
        return k;
    }
    void unite(int u, int v) {
        int par1 = getPar(u), par2 = getPar(v);
        if (par1 == par2) return;
        connected--;
        if (sz[par1] > sz[par2])
            swap(par1, par2);
        if (mp[par2]) {
            s.erase(par2);
        }
        dc = sz[par2] * 1ll * sz[par1];
        sz[par2] += sz[par1];
        sz[par1] = 0;
        par[par1] = par[par2];
        if (!mp[par1]) {
            s.insert(par1);
            mp[par1] = 1;
        }
    }
};


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

    ll n, m;
    cin >> n >> m;
    int u, v;
    vector <PII> edge;
    for (int i = 0; i < m; i++) {
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
        edge.pb({u, v});
    }
    ll temp = (n * (n - 1)) / 2;
    vector <ll> ans;
    ans.pb(temp);
    DSU dsu(n + 1);
    for (int i = m - 1; i >= 1; i--) {
        u = edge[i].first;
        v = edge[i].second;
        dc = 0;
        dsu.unite(u, v);
        temp -= dc;
        ans.pb(temp);
    }
    reverse(all(ans));
    for (auto it : ans) {
        cout << it << endl;
    }
    
    return 0;
}


Measured memory_bytes: 14576
#![allow(non_snake_case)]
#![allow(dead_code)]
#![allow(unused_macros)]
#![allow(unused_imports)]

use std::str::FromStr;
use std::io::*;
use std::collections::*;
use std::cmp::*;

struct Scanner<I: Iterator<Item = char>> {
    iter: std::iter::Peekable<I>,
}

macro_rules! exit {
    () => {{
        exit!(0)
    }};
    ($code:expr) => {{
        if cfg!(local) {
            writeln!(std::io::stderr(), "===== Terminated =====")
                .expect("failed printing to stderr");
        }
        std::process::exit($code);
    }}
}

impl<I: Iterator<Item = char>> Scanner<I> {
    pub fn new(iter: I) -> Scanner<I> {
        Scanner {
            iter: iter.peekable(),
        }
    }

    pub fn safe_get_token(&mut self) -> Option<String> {
        let token = self.iter
            .by_ref()
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
        if token.is_empty() {
            None
        } else {
            Some(token)
        }
    }

    pub fn token(&mut self) -> String {
        self.safe_get_token().unwrap_or_else(|| exit!())
    }

    pub fn get<T: FromStr>(&mut self) -> T {
        self.token().parse::<T>().unwrap_or_else(|_| exit!())
    }

    pub fn vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {
        (0..len).map(|_| self.get()).collect()
    }

    pub fn mat<T: FromStr>(&mut self, row: usize, col: usize) -> Vec<Vec<T>> {
        (0..row).map(|_| self.vec(col)).collect()
    }

    pub fn char(&mut self) -> char {
        self.iter.next().unwrap_or_else(|| exit!())
    }

    pub fn chars(&mut self) -> Vec<char> {
        self.get::<String>().chars().collect()
    }

    pub fn mat_chars(&mut self, row: usize) -> Vec<Vec<char>> {
        (0..row).map(|_| self.chars()).collect()
    }

    pub fn line(&mut self) -> String {
        if self.peek().is_some() {
            self.iter
                .by_ref()
                .take_while(|&c| !(c == '\n' || c == '\r'))
                .collect::<String>()
        } else {
            exit!();
        }
    }

    pub fn peek(&mut self) -> Option<&char> {
        self.iter.peek()
    }
}

fn main() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin.bytes().map(|c| c.unwrap() as char));
    let A: usize = sc.get();
    let B: usize = sc.get();
    let N: usize = sc.get();
    let x = min(N, B - 1);
    println!("{}", (A * x) / B - A * (x / B));
}


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

#define N 100000

vector<bool> n(N+1,true);

void is_prime(){
    n[0]=false;
    n[1]=false;
    for(int i=2;i*i<=N;i++){
        if(n[i]==false)continue;
        for(int j=i+i;j<=N;j+=i){
            n[j]=false;
        }
    }
}

int main(){


    is_prime();
    vector<int> num(N+1,0);
    //for(int i=0;i<10;i++)cout << i << ":"<< n[i] << endl;

    int sum = 0;
    for(int i=2;i<N;i++){
        if(n[i] && n[(i+1)/2])sum++;
        num[i]=sum;
    }

    //for(int i=0;i<10;i++)cout << i << ":"<< num[i] << endl;
    int q;
    cin >> q;
    int l,r;
    //int sum;
    for(int i=0;i<q;i++){
        cin >> l >> r;
        if(n[l] && n[(l+1)/2])cout << num[r]-num[l]+1 << endl;
        else cout << num[r]-num[l] << endl;
    }
}


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

 public class Main{
// taking inputs
static BufferedReader s1;
static BufferedWriter out;
static String read() throws IOException{String line="";while(line.length()==0){line=s1.readLine();continue;}return line;}
static int int_v (String s1){return Integer.parseInt(s1);}
static long long_v(String s1){return Long.parseLong(s1);}
static int[] int_arr() throws IOException{String[] a=read().split(" ");int[] b=new int[a.length];for(int i=0;i<a.length;i++){b[i]=int_v(a[i]);}return b;}
static long[] long_arr() throws IOException{String[] a=read().split(" ");long[] b=new long[a.length];for(int i=0;i<a.length;i++){b[i]=long_v(a[i]);}return b;}
static void assign(){s1=new BufferedReader(new InputStreamReader(System.in));out=new BufferedWriter(new OutputStreamWriter(System.out));}
static long Modpow(long a,long p,long m){long res=1;while(p>0){if((p&1)!=0){res=(res*a)%m;}p >>=1;a=(a*a)%m;}return res;}
static long Modmul(long a,long b,long m){return ((a%m)*(b%m))%m;}
static long ModInv(long a,long m){return Modpow(a,m-2,m);}
static long nck(int n,int r,long m){if(r>n){return 0l;}return Modmul(f[n],ModInv(Modmul(f[n-r],f[r],m),m),m);}
static long[] f;
//......................................@uthor_Alx..............................................

   public static void main(String[] args) throws  IOException{
	        		  assign();
	        		  	int k=int_v(read());
	        		  	
	        		  	out.write((k+k*k+k*k*k)+"");
                      	out.flush();
	        		 
	}
}
	       


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

int main() {
  vector<int>a(3);
  for(int i=0;i<3;i++) cin>>a[i];
  sort(a.begin(),a.end());
  if((2*a[2]-a[1]-a[0])%2==0) cout<<(2*a[2]-a[1]-a[0])/2<<endl;
  else cout<<(2*a[2]-a[1]-a[0]+1)/2+1<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pi 3.14159265359
#define int long long
#define pii pair<int,int>
const int mod=1e9 + 7;
 
int dx[]={-1, 0, 1, 0};
int dy[]={0, -1, 0, 1};
 
 
 
int32_t main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
 

 
  
   int n, k, r, s, p;
  int res = 0;
  string t;
  cin >>n>>k>>r>>s>>p>>t;
  vector<int> scores(n);
  for(int i = 0; i < n; i++) {
    int score;
    switch(t[i]) {
      case 'r':
        score = p;
        break;
      case 's':
        score = r;
        break;
      case 'p':
        score = s;
        break;
    }
    if(i - k >= 0 && scores[i - k] != 0 && t[i] == t[i - k]) {
      score = 0;
    }
    scores[i] = score;
    res += score;
  }
  cout << res;
 
}

Measured memory_bytes: 1232
L, R = map(int, input().split())

res = 1000000007

if R - L + 1 > 2019:
    print(0)
else:
    amari = [i % 2019 for i in range(L, R + 1)]
    l = len(amari)
    for i in range(l):
        a = amari[i]
        for j in range(i + 1, l):
            b = amari[j]
            res = min(res, a * b % 2019)

    print(res)

Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <sstream>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <complex>
#include <vector>
#include <cstdio>
#include <cmath>
#include <time.h>
#define all(c) ((c).begin(),(c).end())
#define rall(c) (c).rbegin(),(c).rend()
#define sort(v,n) sort(v,v+n)
#define vsort(v) sort(v.begin(),v.end())
#define vvsort(v) sort(v.begin(),v.end(),greater<int>())
#define ll long long
#define pb(a) push_back(a)
#define fi first
#define se second
#define inf 999999999
using namespace std;
const ll MOD = 1e9 + 7;
const double PI = acos(-1.0);
//---------------------------------------------------------------------------------------------//
int h, w;
char a[101][101];

int main() {
	cin >> h >> w;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cin >> a[i][j];
		}
	}
	h += 2;
	w += 2;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (i == 0 || i == h - 1)cout << "#";
			else if (j == 0 || j == w - 1)cout << "#";
			else {
				cout << a[i - 1][j - 1];
			}
		}
		cout << endl;
	}
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <fstream>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <limits.h>
#include <math.h>
#include <functional>
#include <bitset>

#define repeat(i,n) for (long long i = 0; (i) < (n); ++ (i))
#define debug(x) cerr << #x << ": " << x << '\n'
#define debugArray(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i] << '\n'
#define debugArrayP(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i].first<< " " << x[i].second << '\n'

using namespace std;

typedef long long ll;
typedef pair<int,int> Pii;
typedef vector<int> vint;
typedef vector<ll> vll;
const ll INF = LLONG_MAX/10;
const ll MOD = 1e9+7;

int main(){
  int N;cin>>N;
  bool isok=true;
  vll U(N),V(N);
  repeat(i,N){
    ll X,Y;
    cin >> X >> Y;
    U[i] = (X+Y);
    V[i] = (X-Y);
    isok &= abs(U[0]+U[i])%2==0;
  }
  if(!isok){
    cout << -1 << endl;
    return 0;
  }
  int m = (abs(U[0])&1? 31:32);
  cout <<m<< endl;
  repeat(i,m){
    if(i==31)cout << 1 << endl;
    else{
      cout << (1<<i) << (i+1<m? " ":"\n");
    }
  }
  repeat(i,N){
    ll UU = (U[i]+(1<<31)-1-!(abs(U[i])&1))/2;
    ll VV = (V[i]+(1<<31)-1-!(abs(V[i])&1))/2;
    string w(m,'R');
    repeat(j,31){
      bool ud = (UU>>j)&1;
      bool vd = (VV>>j)&1;
      if(ud){
        if(vd){
          w[j] = 'R';
        }else{
          w[j] = 'U';
        }
      }else{
        if(vd){
          w[j] = 'D';
        }else{
          w[j] = 'L';
        }
      }
    }
    cout << w << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#!/usr/bin/python3
# -*- coding:utf-8 -*-

import numpy

def main():
  n, k = map(int, input().strip().split())
  Hs = numpy.array([int(line) for line in input().strip().split()], dtype=numpy.int)
  dp = numpy.zeros(n, dtype=numpy.int)
  for i in range(1, n):
    if i - k < 0:
      dp[i] = numpy.min(dp[:i] + numpy.abs(Hs[i] - Hs[:i]))
    else:
      dp[i] = numpy.min(dp[(i-k):i] + numpy.abs(Hs[i] - Hs[(i-k):i]))
  print(dp[-1])


if __name__=='__main__':
  main()

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

struct Node
{
	int data;
	Node* next;
	Node* prev;
};

class List
{
private:
	Node* mother;
public:
    List()
    {
    	mother = new Node;
    	mother->data = -1;
    	mother->next = this->mother;
    	mother->prev = this->mother;
    }

    ~List()
    {
    	Node *tmp;
    	tmp = mother->next;
    	while (1)
    	{
	    	tmp = tmp->next;
    		delete tmp->prev;
	    	if (tmp == mother)
	    		break;
	    }
	    delete mother;
    }

    void Ins(int x)
    {
	    Node *tmp;
    	tmp = this->mother->next;
    	this->mother->next = new Node;
	    this->mother->next->data = x;
    	this->mother->next->next = tmp;
	    this->mother->next->prev = mother;
    	tmp->prev = mother->next;
	
	    return;
    }

    void Del(int x)
    {
    	Node *tmp;
    	tmp = this->mother->next;
    	while (tmp != this->mother)
    	{
    		if (tmp->data == x)
    		{
    			tmp->prev->next = tmp->next;
    			tmp->next->prev = tmp->prev;
    			delete tmp;
    			break;
    		}
    		tmp = tmp->next;
    	}
    	return;
    }
    
    void DelFirst()
    {
    	Node *tmp;
    	tmp = this->mother->next;
    	tmp->next->prev = mother;
    	this->mother->next = tmp->next;
    	delete tmp;
    }

    void DelLast()
    {
    	Node *tmp;
    	tmp = this->mother->prev;
    	this->mother->prev = tmp->prev;
    	tmp->prev->next = mother;
    	delete tmp;
    }

    void Show()
    {
    	Node *tmp;
    	tmp = mother->next;
    	cout << tmp->data;
    	tmp = tmp->next;
    	while (tmp != mother)
    	{
    		cout << " " << tmp->data;
    		tmp = tmp->next;
    	}
    	cout << endl;
    	return;
    }
};


int main()
{
	int n, x;
	char command[20];
	List list;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> command;
		if (!strcmp(command, "insert"))
		{
			cin >> x;
			list.Ins(x);
		}
		else if (!strcmp(command, "delete"))
		{
			cin >> x;
			list.Del(x);
		}
		else if (!strcmp(command, "deleteFirst"))
			list.DelFirst();
		else
			list.DelLast();
	}
	list.Show();

	return 0;
}


Measured memory_bytes: 34356
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for (int i = 1; ; i++) {
            int x = sc.nextInt();
            if(x == 0) {
                break;
            }
            System.out.printf("Case %d: %d\n",i,x);
        }
    }
}


Measured memory_bytes: 61140
blue = []
red = []
n = int(input())
for i in range(n):
    blue.append(input())

m = int(input())
for j in range(m):
    red.append(input())

ans = 0
red_set = set(red)
blue_set = set(blue)
for b in blue_set:
 for r in red_set:
     ans = max(ans,blue.count(b)-red.count(b))
print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#include<random>
using namespace std;
using ll=long long;
using ld=long double;
using P=pair<ll,ll>;
#define MOD 1000000007LL
#define INF 1000000000ll
#define EPS 1e-10
#define FOR(i,n,m) for(ll i=n;i<(ll)m;i++)
#define REP(i,n) FOR(i,0,n)
#define DUMP(a) REP(d,a.size()){cout<<a[d];if(d!=a.size()-1)cout<<" ";else cout<<endl;}
#define ALL(v) v.begin(),v.end()
#define UNIQUE(v) sort(ALL(v));v.erase(unique(ALL(v)),v.end());
#define pb push_back

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll N;
	cin>>N;
	vector<string> w(N);
	REP(i,N) cin>>w[i];
	vector<ll> alp(26,INF);
	ll ans=0;
	vector<ll> dp(N,INF*INF);
	dp[0]=0;
	alp[w[0][0]-'a']=min(alp[w[0][0]-'a'],dp[0]);
	FOR(i,1,N) {
		dp[i]=min(alp[w[i][0]-'a'],dp[i-1]+1);
		alp[w[i][0]-'a']=min(alp[w[i][0]-'a'],dp[i]);
	}
	cout<<dp[N-1]+1<<endl;
	return 0;
}




Measured memory_bytes: 9208
import Control.Monad
import Data.List
import Data.Function
import Data.Maybe
import qualified Data.ByteString.Char8 as BC8

main :: IO ()
main = do
  [n, k] <- (map read . words) <$> getLine :: IO [Int]
  -- rows <- replicateM n $ map (fst . fromJust . BC8.readInt) . BC8.words <$> BC8.getLine :: IO [[Int]]
  rows <- replicateM n $ (map read . words) <$> getLine :: IO [[Int]]
  let sorted = sortBy (compare `on` head) rows
  print =<< solve k 0 0 sorted

solve k i a' rows
  | k <= i = return a'
  | otherwise = let [a, b]:rows' = rows in solve k (i + b) a rows'


Measured memory_bytes: 148860
#include<iostream>
#include<vector>
#include<algorithm>
#include<iterator>
using namespace std ;
int main()
{
    int arr[55],n;
    cin >> n ;
    for(int i=0;i<n;i++)
    {
        cin >> arr[i];
    }
    sort(arr,arr+n);
    double x = arr[0];
    for(int i=1;i<n;i++)
    {
        int z = arr[i];
        x = (double)(x+z)/2;
    }
    cout << x << endl;
    return 0;
}

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

using namespace std;

int main() {
	int N, M, X;
	cin >> N >> M >> X;
	vector<int>A(M);

	for (int i = 0; i < M; i++) {
		cin >> A[i];
	}

	int left = 0, right = 0;
	for (int i = 0; i < M; i++) {
		if (A[i] < X) {
			left++;
		}
		else {
			right++;
		}
	}

	cout << min(left, right) << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <functional>
#include <set>
#include <sstream>
#include <map>

using namespace std;

const double eps=1e-10;

int main()
{
	double v;
	while(cin>>v){
		unsigned long long l=1,r=1e16,h;

		for(int i=0;i<1000;i++){

//			cout<<l<<" "<<r<<endl;

			h=(l+r)/2;
			double vv=2.0*9.8*(5*h-5);

			if(v*v>vv) l=h;
			else if(v*v<vv) r=h;
		}

		if( v*v<=2.0*9.8*(5*l-5) ) cout<<l<<endl;
		else cout<<r<<endl;

	}

	return 0;
}

Measured memory_bytes: 1216
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const ll INF = 1LL << 60;

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

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

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

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

using namespace std;

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

    vector<int> reverse(n);
    for(int j=0;j<n;j++){
        reverse[a[j]-1]= j+1;
    }
    for(int i=0;i<n;i++){
        cout << reverse[i] << endl;
    }
}

Measured memory_bytes: 1536
#include <stdio.h>
#define N_MAX 100

int a[N_MAX];

int n, m;
int i;

int main(void){
	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++) scanf("%d", &a[i]);

	for (i = 1; i <= m; i++) {
		int j;
		for (j = 0; j + 1 < n; j++) {
			if (a[j] % i > a[j+1] % i) {
				a[j+1] ^= a[j];
				a[j] ^= a[j+1];
				a[j+1] ^= a[j];
			}
		}
	}

	for (i = 0; i < n; i++) printf("%d\n", a[i]);

	return 0;
}

Measured memory_bytes: 596
use std::cmp;

const INF: u64 = 1e15 as u64;

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let h: usize = sc.read();
    let w: usize = sc.read();
    let c: Vec<Vec<char>> = (0..h).map(|_| sc.chars()).collect();
    let mut map: Vec<Vec<char>> = vec![vec!['a'; h]; w];
    for i in 0..h {
        for j in 0..w {
            map[j][i] = c[i][j];
        }
    }

    let mut ans = 0;
    for i in 1..w {
        ans += solve(&map[i - 1], &map[i]);
    }
    println!("{}", ans);
}

fn solve<T: cmp::PartialEq>(a: &Vec<T>, b: &Vec<T>) -> u64 {
    let n = a.len();
    let mut cost = vec![vec![0; n + 1]; n + 1];
    for removed in 0..(n + 1) {
        let mut c = 0;
        for i in 0..(n - removed) {
            if a[i + removed] == b[i] {
                c += 1;
            }
        }
        cost[0][removed] = c;
    }
    for removed in 0..(n + 1) {
        let mut c = 0;
        for i in 0..(n - removed) {
            if a[i] == b[i + removed] {
                c += 1;
            }
        }
        cost[removed][0] = c;
    }

    for d in 0..n {
        for i in 0..n {
            if i + 1 + d > n { break; }
            cost[i + 1][i + 1 + d] = cost[i][i + d] - if a[n - 1 - i] == b[n - i - 1 - d] { 1 } else { 0 };
            cost[i + 1 + d][i + 1] = cost[i + d][i] - if a[n - 1 - d - i] == b[n - 1 - i] { 1 } else { 0 };
        }
    }


    let mut dp = vec![vec![INF; n + 1]; n + 1];
    dp[0][0] = 0;
    for i in 0..n {
        for j in 0..n {
            dp[i][j + 1] = cmp::min(dp[i][j + 1], dp[i][j] + cost[i][j]);
            dp[i + 1][j] = cmp::min(dp[i + 1][j], dp[i][j] + cost[i][j]);
        }
    }

    let mut ans = INF;
    for i in 0..n {
        ans = cmp::min(ans, dp[n][i]);
        ans = cmp::min(ans, dp[i][n]);
    }
    ans
}

pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n')
            .take_while(|&b| b != b' ' && b != b'\n')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


Measured memory_bytes: 6396
def solve(N, As):
    d = 0
    s = sum(As)
    m = 10 ** 15
    for a in As[:N - 1]:
        d += a
        m = min(m, abs(d - (s - d)))
    return abs(m)


if __name__ == "__main__":
    N = int(input())
    As = list(map(int, input().split(" ")))
    print(solve(N, As))


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

H, W, D = map(int, input().split())
grid = []
for i in range(H):
    grid.append(list(map(int, input().split())))

place = []


for i in range(H):
    for j in range(W):
        place.append([grid[i][j], i, j])
place.sort()


classify = [[0] for i in range(D)]

for i in range(D):
    for j in range(i, H*W-D, D):
        classify[(i+1)%D].append(abs(place[j+D][1]-place[j][1])+abs(place[j+D][2]-place[j][2]) + classify[(i+1)%D][-1])

Q = int(input())
for _ in range(Q):
    L, R = map(int, input().split())
    ans = str(classify[R%D][(R-1)//D] - classify[L%D][(L-1)//D])
    print(ans)


Measured memory_bytes: 69724
#include<bits/stdc++.h> 
using namespace std;
typedef long long int ll;
#define MOD 1000000007
#define fo(i,k,n) for(i=k;i<=n;i++)
#define endl '\n'
ll dp[101][100001];
//memoisation
ll knapsnack(ll* w,ll* v,ll n,ll mw){
	if(dp[n][mw]>-1) return dp[n][mw];
	if(n==0) return 0;//no item left
	if(mw==0) return 0;//no more capacity
	ll op1 = knapsnack(w,v,n-1,mw);
	ll op2 = LLONG_MIN;
	if(w[n-1]<=mw) op2 = v[n-1]+knapsnack(w,v,n-1,mw-w[n-1]);
	return dp[n][mw]=max(op1,op2);
}
//tabulation
ll knapsnacki(ll* w,ll* v,ll n,ll mw){
	ll i,j;
	fo(i,0,mw) dp[0][i]=0;
	fo(i,0,n) dp[i][0]=0;
	fo(i,1,n){
		fo(j,1,mw){
			dp[i][j] = dp[i-1][j];
			if(w[i-1]<=j) dp[i][j] = max(dp[i][j],v[i-1]+dp[i-1][j-w[i-1]]);
		}
	}
	return dp[n][mw];
}
//tabulation memory optimised
ll knapsnacki2(ll* w,ll* v,ll n,ll mw){
	ll i,j;
	ll dp2[2][mw+1];
	fo(i,0,mw) dp2[0][i]=0;
	dp2[1][0]=0;
	ll idx=1;
	fo(i,1,n){
		fo(j,1,mw){
			dp2[idx][j] = dp2[idx^1][j];
			if(w[i-1]<=j) dp2[idx][j] = max(dp2[idx][j],v[i-1]+dp2[idx^1][j-w[i-1]]);
		}
		idx^=1;
	}
	return dp2[idx^1][mw];
}
//for large weights
ll dpi3[100001][101];
ll knapsnacki3(ll* w,ll* v,ll n,ll mw){
	ll i,j;
	for(i=0;i<=n;i++) dpi3[0][i]=0;
	for(i=1;i<=100000;i++) dpi3[i][n]=mw+1;
	for(i=1;i<=100000;i++){
		for(j=n-1;j>=0;j--){
			dpi3[i][j] = dpi3[i][j+1];
			if(i-v[j]>=0) dpi3[i][j] = min(dpi3[i][j],w[j]+dpi3[i-v[j]][j+1]);
		}
	}
	ll ans = 0;
	for(i=0;i<=100000;i++) if(dpi3[i][0]>0&&dpi3[i][0]<=mw) ans = max(ans,i);
	return ans;
}
void solve(){
	ll i,j,n,mw;
	cin>>n>>mw;
	ll* w = new ll[n];
	ll* v = new ll[n];
	fo(i,0,n-1){
		cin>>w[i]>>v[i];
	}
	memset(dp,-1,sizeof(dp));
	cout<<knapsnacki3(w,v,n,mw)<<endl;
	//cout<<knapsnacki2(w,v,n,mw)<<endl;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	ll t;
	t=1;//cin>>t;
	while(t--){
		solve();
	}
	return 0;
}


Measured memory_bytes: 158208
#include <bits/stdc++.h>
#include <iostream>
#include <math.h>
using namespace std;
int main() {
    int N, M;
    cin >> N >> M;
    vector<vector<int>> switches(M, vector<int>(N, 0));
    vector<int>mod_lis(M);
    int sum = 0;
    for (int i=0; i<M; i++) {
        int switch_count;
        cin >> switch_count;
        for (int j=0; j<switch_count; j++) {
            int k;
            cin >> k;
            switches[i][k-1] = 1;
        }
    }

    for (int i=0; i<M; i++) {
        cin >> mod_lis.at(i);
    }

    int count = 0;
    for (int bit=0; bit < (1<<N); bit++) {
        bool all_on = true;
        for (int i=0; i<M; i++) {
            int on_count = 0;
            // ランプの数だけ試す。
            int mod = mod_lis[i];
            for (int j=0; j<switches[i].size(); j++) {
                if (switches[i][j] == 1 && (bit & 1<<j)) {
                    on_count += 1;
                }
            }

            if (on_count % 2 != mod) {
                all_on = false;
                break;
            }
        }

        if (all_on) {
            count += 1;
        }
    }

    cout << count << endl;
    return 0;
}

Measured memory_bytes: 256
#pragma warning(disable:4996)

#include <stdio.h>
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <complex>
#include <iterator>
#include <random>
#include <time.h>
#include <tuple>
#include <functional>
#include <list>
#include <limits.h>
using namespace std;

int N, K, L;
vector<vector<int> > adj[2];
vector<int> comp[2];
int ccnt = 0;

void bfs(int t) {
	ccnt = 0;
	comp[t] = vector<int>(N, -1);
	for(int i = 0; i < N; i++) {
		if(comp[t][i] != -1) continue;
		queue<int> q;
		q.push(i);
		comp[t][i] = ccnt;
		while(!q.empty()) {
			int u = q.front(); q.pop();

			for(int i = 0; i < adj[t][u].size(); i++) {
				int v = adj[t][u][i];
				if(comp[t][v] == -1) {
					q.push(v);
					comp[t][v] = ccnt;
				}
			}
		}
		ccnt++;
	}
}

struct Info {
	int a, b, c;
	Info(){}
	Info(int a_, int b_, int c_) : a(a_), b(b_), c(c_) {}
	bool operator <(const Info &i) const {
		return a < i.a || (a == i.a && b < i.b);
	}
};
vector<Info> info;
vector<int> ans;

int main() {
	scanf("%d %d %d", &N, &K, &L);
	adj[0].resize(N);
	for(int i = 0; i < K; i++) {
		int a, b; scanf("%d %d", &a, &b);
		a--; b--;
		adj[0][a].push_back(b);
		adj[0][b].push_back(a);
	}
	adj[1].resize(N);
	for(int i = 0; i < L; i++) {
		int a, b; scanf("%d %d", &a, &b);
		a--; b--;
		adj[1][a].push_back(b);
		adj[1][b].push_back(a);
	}
	bfs(0);
	bfs(1);
	info.resize(N);
	for(int i = 0; i < N; i++) info[i] = Info(comp[0][i], comp[1][i], i);
	sort(info.begin(), info.end());
	int s = 0;
	ans.resize(N);
	for(int i = 1; i <= N; i++) {
		if(i == N || info[i - 1].a != info[i].a || info[i - 1].b != info[i].b) {
			for(int j = s; j < i; j++) {
				ans[info[j].c] = i - s;
			}
			s = i;
		}
	}
	for(int i = 0; i < N; i++) {
		cout<<ans[i]<<' ';
	}
}

Measured memory_bytes: 20516
#include <stdio.h>
#include <stdlib.h>
int puz[3][3];
int tmp[3][3];
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
void empty(int *x,int *y) {
  int i,j;
  for(i=0; i<3; i++) {
    for(j=0; j<3; j++) {
      if(!puz[i][j]) {
        *x = j;
        *y = i;
        return;
      }
    }
  }
}
void swap(int *a,int *b){
  int tmp;
  tmp = *a;
  *a = *b;
  *b = tmp;
}
int cal(){
  int i,a,sum=0;
  for(i=0; i<9; i++){
    a = puz[i/3][i%3];
    if(a){
      a--;
      sum += abs(i/3 - a/3) + abs(i%3 - a%3);
    }
  }
  return sum;
}
int dfs(int x,int y,int p,int dep,const int lim){
  int i,h,nx,ny,res;
  h = cal();
  if(h==0) return dep;
  if(dep+h>lim) return -1;
  for(i=0; i<4; i++){
    nx = x+dx[i];
    ny = y+dy[i];
    if(~p && i==(p+2)%4) continue;
    if(!(0<=nx && nx<3 && 0<=ny && ny<3)) continue;
    swap(&puz[y][x],&puz[ny][nx]);
    res = dfs(nx,ny,i,dep+1,lim);
    if(~res) return res;
    swap(&puz[y][x],&puz[ny][nx]);
  }
  return -1;
}
int main() {
  int i,j,ans,x,y,l;
  
  for(i=0; i<3; i++){
    for(j=0; j<3; j++) scanf("%d",&puz[i][j]);
  }
  
  empty(&x,&y);
  for(l=0; l<100; l++){
    for(i=0; i<3; i++){
      for(j=0; j<3; j++) tmp[i][j] = puz[i][j];
    }
    
    ans = dfs(x,y,-1,0,l);
    if(ans!=-1){
      printf("%d\n",ans);
      break;
    }
    
    for(i=0; i<3; i++){
      for(j=0; j<3; j++) puz[i][j] = tmp[i][j];
    }
    
    ans = -1;
    if(l==99) printf("%d\n",ans);
  }

  return 0;
}


Measured memory_bytes: 2104
import itertools

n = int(input())

x_list = []
y_list = []
cnt = 0
distance = 0

for i in range(n):
    x,y = map(int,input().split())
    x_list.append(x)
    y_list.append(y)

for a in itertools.permutations(range(n)): #順列を生成して、それらに対して処理
    cnt += 1
    for i in range(len(a)-1):
        #　各順列に対する処理
        distance += ((x_list[a[i]]-x_list[a[i+1]])**(2) + (y_list[a[i]]-y_list[a[i+1]])**(2))**(1/2)
ans = distance/cnt
print(ans)

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

#define int long long
#define rep(i,a,b) for(int i = a; i < b; i++)
const int mod = 1e9 + 7;

int dp[100010][13];

signed main() {
    string S;
    cin >> S;
    int N = S.size();
    rep(i,0,N) rep(j,0,13) dp[i][j] = 0;
    dp[0][0] = 1;

    rep(i,0,N) {
        rep(j,0,13) {
            if (S[i] == '?') {
                rep(k,0,10) {
                    int l = (10*j + k) % 13;
                    dp[i+1][l] += dp[i][j];
                    dp[i+1][l] %= mod;
                }
            }
            else {
                int l = (10*j + (S[i] - '0')) % 13;
                dp[i+1][l] += dp[i][j];
                dp[i+1][l] %= mod;
            }
        }
    }
    int ans = dp[N][5];
    cout << ans << endl;
}

Measured memory_bytes: 10624