akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long int
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
 
#define mp make_pair
#define pb push_back
#define ld long double
#define f first
#define s second
const ll N =(1e6) ;
const ll mod = (1e9+7);
 	
 int main(){
 	ll n ,W ; 
 	cin >> n >>W;

 	ll dp[n+1][W+1]={};
 	
 	ll w[n+1] , v[n+1] ;
 	
 	for (ll i = 1; i <= n; ++i)
 	{
 		cin >> w[i] >> v[i];
 	}
 
  	for (ll i = 1; i <=W ; ++i)
	{
		if(w[1] <= i)
			dp[1][i] = v[1];
	}  	 		 	 
  	
  	for (ll i = 2; i <=n ; ++i)
  	{
  		for (ll j = 1; j <=W ; ++j)
  		{
  			if(w[i] <= j)
  				dp[i][j] = max(dp[i-1][j] , v[i] + dp[i-1][j - w[i]]);
  			else
  				dp[i][j] = dp[i-1][j];
  		}
  	}

  	/*for (ll i = 0; i <= n; ++i)
  	{
  		for (ll j = 0; j <=W; ++j)
  		{
  			cout<<dp[i][j]<<" ";
  		}
  		cout<<endl;
  	}*/
  	cout<<dp[n][W];
}



Measured memory_bytes: 79104
#include<bits/stdc++.h>
#define mo 998244353
#define N 500005
using namespace std;
int fac[N],inv[N],n,k;
int C(int x,int y){
	if (x>=y)
		return 1ll*fac[x]*inv[y]%mo*inv[x-y]%mo;
	return 0;
}
int calc(int v,int x,int y){
	return (C(x+y,x)+mo-C(x+y,(y-v+mo)%mo))%mo;
}
int main(){
	fac[0]=inv[0]=inv[1]=1;
	for (int i=2;i<N;i++)
		inv[i]=1ll*(mo-mo/i)*inv[mo%i]%mo;
	for (int i=1;i<N;i++){
		fac[i]=1ll*fac[i-1]*i%mo;
		inv[i]=1ll*inv[i-1]*inv[i]%mo;
	}
	scanf("%d%d",&n,&k);
	if (n>k) return puts("0"),0;
	int ans=0;
	for (int R=k-k/2;R<=k;R++){
		int B=k-R;
		if (R==B)
			ans=(ans+calc(R-n+1,R,B-1))%mo;
		else if (B-R<n)
			ans=(ans+calc(R-n+1,R,B))%mo;
		else ans=(ans+C(R+B,R))%mo; 
	}
	printf("%d",ans);
}

Measured memory_bytes: 4096
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
  ll n,i;
  string s;
  set<string>vec; 
  cin>>n;
  for(i=0;i<n;i++)
    {
      cin>>s;
      vec.insert(s);
    }
   cout<<vec.size()<<endl;
   
}

Measured memory_bytes: 19256
n = int(input())
a,b = map(int, input().split())
c = list(map(int, input().split()))
d = 0
e = 0
f = 0
for i in c:
  if i <= a:
    d += 1
  elif i > b:
    f += 1
  else:
    e += 1
print(min(min(d,e),f))

Measured memory_bytes: 3060
#include<bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
int main(){
  string s;cin >> s;
  int n = s.size(),i,now = 0;
  for(i=0;i<n;i++) now += s[i]-'0';
  cout << ((now%9 == 0) ? "Yes\n":"No\n");
}

Measured memory_bytes: 3756
#include <bits/stdc++.h>
using namespace std;
int main(void){
    // Your code here!
    int n;
    cin>>n;
    vector <int> num(n);
    for(int i=0;i<n;i++){
        cin>>num[i];
    }
    
    int  ct=0,minv=1e9; 
    for(int i=0;i<n;i++){
        minv=min(minv,num[i]);
        if(minv==num[i]) ct++;
    }
    
    cout<<ct<<endl;
}


Measured memory_bytes: 1024
#include<stdio.h>
#include<stdlib.h>
#define MAX 2000001
#define VMAX 10000

int B[MAX], C[MAX];

// 1 CountingSort(A, B, k)
// 2     for i = 0 to k
// 3         C[i] = 0
// 4
// 5     /* C[i] に i の出現数を記録する */
// 6     for j = 1 to n
// 7         C[A[j]]++
// 8
// 9     /* C[i] に i 以下の数の出現数を記録する*/
// 10    for i = 1 to k
// 11        C[i] = C[i] + C[i-1]
// 12
// 13    for j = n downto 1
// 14        B[C[A[j]]] = A[j]
// 15        C[A[j]]--
void countingSort(int A[], int B[], int k, int n){
  int i, j;
  for(i = 0; i <= k; i++){
    C[i] = 0;
  }
  for(j = 1; j <= n; j++){
    C[A[j]]++;
  }
  for(i = 1 ; i <= k; i++){
    C[i] =  C[i] + C[i-1];
  }
  for(j = n; j >= 1; j--){
    B[C[A[j]]] = A[j];
    C[A[j]]--;
  }

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

}

int main(){
  int A[MAX];
  int n, i, j, k = 0;
  scanf("%d", &n);

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

  countingSort(A, B, k, n);

  return 0;
}



Measured memory_bytes: 17392
#include<bits/stdc++.h>
#define maxn 55
using namespace std;

int n,a[maxn],cnt=0;
int main()
{
	cin>>n;
	for(int i=1;i<=n;++i) 
	{
		cin>>a[i];
		if(a[i]!=i) cnt++;
	}
	if(cnt==0 || cnt==2) cout<<"YES";
	else cout<<"NO";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rng(i, a, b) for (int i = int(a); i < int(b); i++)
#define rep(i, b) rng(i, 0, b)
#define gnr(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define per(i, b) gnr(i, 0, b)
#define bg begin()
#define ed end()
#define all(x) x.bg, x.ed
#define vi vector<int>
template <class t, class u>
bool chmax(t &a, u b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class t, class u>
bool chmin(t &a, u b)
{
    if (b < a)
    {
        a = b;
        return true;
    }
    return false;
}

signed main()
{
    string s;
    int q;
    cin >> s >> q;
    deque<string> ds;
    ds.push_back(s);
    bool is_reversed = false;
    rep(i, q)
    {
        int a;
        cin >> a;
        if (a == 1)
        {
            is_reversed = !is_reversed;
        }
        else
        {
            int f;
            string c;
            cin >> f >> c;
            if (f == 1)
            {
                if (!is_reversed)
                {
                    ds.push_front(c);
                }
                else
                {
                    ds.push_back(c);
                }
            }
            else
            {
                if (is_reversed)
                {
                    ds.push_front(c);
                }
                else
                {
                    ds.push_back(c);
                }
            }
        }
    }
    if (!is_reversed)
    {
        for (auto &i : ds)
        {
            cout << i;
        }
        cout << endl;
    }
    else
    {
        for (auto i = ds.rbegin(); i != ds.rend(); i++)
        {
            string s = *i;
            reverse(all(s));
            cout
                << s;
        }
        cout << endl;
    }

    return 0;
}

Measured memory_bytes: 10216
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
using namespace std;
using ll = long long;
const ll INF = 10e9;

int main(){
  ll a,b,v,w,t;
  cin>>a>>v>>b>>w>>t;
  if (v<=w){
    cout << "NO" << endl;
    return 0;
  }
  else{
    if ( abs(a-b) <= t*(v-w) ){
      cout << "YES" << endl;
      return 0;
    }
    else{
      cout << "NO" << endl;
      return 0;
    }
  }
}

Measured memory_bytes: 3632
#include <stdio.h>

int main() {
	int h, w;
	int i, j;
	while (1) {
		scanf("%d %d ", &h, &w);
		if (h == 0 && w == 0)break;
		for (i = 0; i<h; i++) {
			for (j = 0; j<w; j++) {
				if ((i % 2 == 0 && j % 2 == 0) || (i % 2 == 1 && j % 2 == 1)) {
					printf("#");
				}
				else {
					printf(".");
				}
			}
			printf("\n");
		}
		printf("\n");
	}

	return 0;
}

Measured memory_bytes: 2576
import sys, math, itertools, collections, bisect 
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8') 
inf = float('inf') ;mod = 10**9+7 
mans = inf ;ans = 0 ;count = 0 ;pro = 1

a = int(input())
b = int(input())
c = int(input())
x = int(input())
for i in range(a+1):
    for j in range(b+1):
        for k in range(c+1):
            if i*500 + j*100 + k*50 == x:
                ans += 1
print(ans)

Measured memory_bytes: 39536
#include <iostream>

using namespace std;

constexpr int MAX = 200;
constexpr int INF = (1 << 29);

int main()
{
    int N, u, v, d[MAX][MAX];
    string s;

    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            d[i][j] = (i != j) * INF;
        }
    }
    
    cin >> N;    
    for (int i = 0; i < N; i++) {
        cin >> u >> s >> v;
        u--; v--; v += MAX / 2;
        if (s == "lock") swap(u, v);
        d[u][v] = -1;
    }

    for (int k = 0; k < MAX; k++) {
        for (int i = 0; i < MAX; i++) {
            for (int j = 0; j < MAX; j++) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
    
    bool res = 0;
    for (int i = 0; i < MAX; i++) {
        if (d[i][i] < 0) {
            res = 1;
            break;
        }
    }
    cout << res << endl;    
    return 0;
}

Measured memory_bytes: 3348
package main

import (
	"fmt"
)

func main() {
	var r int
	fmt.Scan(&r)
	if r < 1200 {
		fmt.Println("ABC")
	} else if r < 2800 {
		fmt.Println("ARC")
	} else {
		fmt.Println("AGC")
	}
}


Measured memory_bytes: 512
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextRuneSlice() []rune {
	return []rune(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func main() {
	sc := NewScanner()
	N, M := sc.nextInt(), sc.nextInt()
	set := make(map[int][]int)
	for i := 0; i < M; i++ {
		a, b := sc.nextInt(), sc.nextInt()
		set[a-1] = append(set[a-1], b-1)
		set[b-1] = append(set[b-1], a-1)
	}
	var count int
	var search func(next int, seen []bool)
	search = func(current int, seen []bool) {
		seen[current] = true

		visitedAll := true
		for i := 0; i < N; i++ {
			if !seen[i] {
				visitedAll = false
			}
		}
		if visitedAll {
			count++
			return
		}
		for _, next := range set[current] {
			if seen[next] {
				continue
			}
			nseen := make([]bool, N)
			copy(nseen, seen)
			search(next, nseen)
		}
	}
	search(0, make([]bool, N))
	fmt.Println(count)
}


Measured memory_bytes: 768
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size()) //unsignedのサイズをint型に変換
#define dump(x)  cerr << #x << " = " << (x) << endl;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL; 

 
long long int gcd(long long int a, long long int b) {
	if (a < b)swap(a, b);
	while (b) {
			a %= b;
			swap(a, b);
		}
		return a;
	}


//ここから書き始める
int main(int argc, char const *argv[])
{
	int N, M;
	cin >> N >> M;
	string S, T;
	cin >> S >> T;

	auto nmgcd = gcd(N,M);
	int n = N / nmgcd;
	int m = M/ nmgcd;

	int loop = nmgcd;
	int flag = 0;


	FOR(i, 0, loop)
	{
		if(S[i * n] != T[i * m])
		{
			cout << -1 << endl;
			flag = 1;
			break;
		}

	}
	if(flag == 0)
	{
		LL before_ans = N;
		LL before_ans1 = m;
		LL ans = before_ans1 * before_ans;
		cout <<  ans << endl;
	}



}


Measured memory_bytes: 512
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#pragma warning(disable : 4996)
const int mod = 1000000007;
using namespace std;
int n, m, x[100009], y[100009];
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) scanf("%d", &x[i]);
	for (int i = 0; i < m; i++) scanf("%d", &y[i]);
	long long rn = 0, rm = 0;
	for (int i = 0; i < n - 1; i++) rn = (rn + 1LL * (i + 1) * (n - i - 1) % mod * (x[i + 1] - x[i])) % mod;
	for (int i = 0; i < m - 1; i++) rm = (rm + 1LL * (i + 1) * (m - i - 1) % mod * (y[i + 1] - y[i])) % mod;
	cout << 1LL * rn * rm % mod << endl;
	return 0;
}

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

int main(){
  int N,X;
  cin>>N>>X;
  std::vector<int> v(N);
  for(int i=0;i<N;i++){
    cin>>v[i];v[i]-=X;
  }
  int ans;
  ans=__gcd(v[0],v[1]);
  for(int i=1;i<N;i++){
    ans=__gcd(ans,v[i]);
  }
  cout<<abs(ans)<<endl;
}


Measured memory_bytes: 640
#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <functional>
#include <string>
#include <cstdlib>
#include <numeric>
#include <cstdbool>
#include <map> 
#include<set>
#include<queue>

typedef long long ll;


#define rep(i,n) for(ll i=0;i<n;i++)
using namespace std;

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 long long INF = 1000000000000000;
const ll inf = -1e18;
typedef pair<int, int> P;
ll ma = 1000000000 + 7;
ll h, w, n,k,m; string s,t;
char maze[60][60];
int dis[101][101]; int graph[52][52]; bool vis[52];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
ll gcd(ll x, ll y) {
	if (x % y == 0) return y;
	return gcd(y, x % y);

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

int main() {
	cin >> s;
	int n = s.length(); ll res = 0;
	for (int bit = 0; bit < (1 << (s.size() - 1)); bit++) {
		ll num = s[0] - '0';
		for (int i = 0; i < s.size() - 1; i++) {
			if (bit & 1 << i) {
				res += num;
				num = 0;
			}
			num = num * 10 + s[i + 1] - '0';
		}
		res += num;
	}
	cout << res << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
void dfs(int p,int x,int r);

using Graph = vector<vector<int>>;

Graph G;

vector<long long> ans,sum;

int main(){
	// sengen
	int n,q;
	// nyuryoku
	cin >> n >> q;
	G.assign(n,vector<int>());
	ans.assign(n,0);
	int a,b;
	for(int i=0;i<n-1;i++){
		cin >> a >> b;
		G[a-1].push_back(b-1);
		G[b-1].push_back(a-1);
	}
	// keisan
	int p,x;
	sum.assign(n,0);
	for(int i=0;i<q;i++){
		cin >> p >> x;
		p--;
		sum[p] += x;
	}
	dfs(0,sum[0],-1);
	// syutsuryoku
	for(int i=0;i<n;i++){
		cout << ans[i] << ' ';
	}
}

void dfs(int p,int x,int r){
	ans[p] += x;
	for(auto np:G[p]){
		if(np == r){
			continue;
		}
		dfs(np,x+sum[np],p);
	}
}

Measured memory_bytes: 25856
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
#define lp(var,start,end) for (ll var = start; var <end ; ++var)
#define rlp(var,start,end) for(ll var = start; var>=end ; var--)
#define pli pair<ll, int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pq priority_queue;

int main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	double a,b,h,m;
	cin>>a>>b>>h>>m;
	double deg= fabs(30*h+m/2-6*m);
	if(deg>180)
		deg=360-deg;
	double rad= 0.01745329252*deg;
	double c= sqrt(a*a+b*b-2*a*b*cos(rad));
	printf("%0.10f\n", c);
	return 0;
}

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

int main() {
  int n; cin >> n;
  vector<ll> a(n);
  for (auto & e : a) cin >> e;
  sort(a.begin(), a.end());

  ll s = a[0];
  int c = 1;
  for (int i = 1; i < n; ++i) {
    if (s * 2 < a[i]) {
      c = 1;
    } else {
      ++c;
    }
    s += a[i];
  }

  cout << c << endl;
  
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
 
#define pii pair<int,int>
#define pll pair<ll,ll>
#define eb emplace_back
#define ll long long
#define nl '\n'
#define in() ( { int a ; scanf("%d",&a); a; } )
 
const int N = 1e5 + 9;
const int mod = 1e9 + 7;
//int dx[]={1,0,-1,0,1,-1,-1,1};
//int dy[]={0,1,0,-1,1,1,-1,-1};
vector<int> graph[N];
vector<int> color(N);
vector<int> frnds;
vector<int> blocked(N);

int bfs(int src, int colors)
{
    deque<int> dq;
    dq.eb(src);
    color[src] = colors;
    int size = 1;
    while(!dq.empty()){
        int ma_src = dq.front();
        dq.pop_front();
        for(auto adj:graph[ma_src]){
            if(color[adj] == -1){
                color[adj] = colors;
                size++;
                dq.eb(adj);
            }
        }
    }
    return size;
}
int main()
{
    int n, m, k, i, u, v;
    cin >> n >> m >> k;
    for (i = 0; i < m; i++){
        cin >> u >> v;
        graph[u].eb(v);
        graph[v].eb(u);
    }
    int colors = 0;
    fill(color.begin(), color.end(), -1);
    frnds.eb(0);
    for (i = 1; i <= n; i++)
    {
        if(color[i] != -1){
            continue;
        }
        colors++;
        frnds.eb(bfs(i, colors));
    }
    for (i = 0; i < k; i++){
        cin >> u >> v;
        if(color[u] == color[v]){
            blocked[u]++;
            blocked[v]++;
        }
    }
    for (i = 1; i <= n; i++){
        //cout << frnds[color[i]] << nl;
        cout << frnds[color[i]] - 1 - graph[i].size() - blocked[i] << " ";
    }
}

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

long long n, k;
long long zero, two, ans = 0;

int main() {
  cin >> n >> k;
  zero = n / k;
  two = (n + k / 2) / k;
  ans = zero * zero * zero;
  if(k % 2 == 0) ans += two * two * two;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 384
#include <cstdio>
#include <stack>
#include <algorithm>
using namespace std;
 
int n;
 
int main(void){
    stack<int> s;
    char c;
    while(scanf("%c",&c)!=EOF){
        if(c=='+'){
            int a=s.top();
            s.pop();
            int b=s.top();
            s.pop();
            s.push(a+b);
        }
        if(c=='-'){
            int a=s.top();
            s.pop();
            int b=s.top();
            s.pop();
            s.push(b-a);
        }
        if(c=='*'){
            int a=s.top();
            s.pop();
            int b=s.top();
            s.pop();
            s.push(a*b);
        }
        if(c>='0' && c<='9'){
            int d=c-'0';
            while(1){
                scanf("%c",&c);
                if(c>='0' && c<='9')d=d*10+(c-'0');
                else break;
            }
            s.push(d);
        }else scanf("%*c");
    }
    printf("%d\n",s.top());
    return 0;
}


Measured memory_bytes: 2768
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
int main(){
    ll a,b,c;
    cin>> a>> b  >>c;
    if(a%2 == 0 || b%2 == 0 || c%2 == 0){
        cout << 0 <<endl;
        return 0;
    }
    else{
        cout << min(b*c,(min(a*c,a*b))) << endl;
    }
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

void coinSort(int* coins, const int count);
int dp_coin(const int target, const int* coins, const int coinCount);

int main()
{
	int value;
	int coin_val;
	int i, ans;
	int* coins;
	
	scanf("%d %d", &value, &coin_val);
	coins = (int *)malloc(sizeof(int) * coin_val);
	
	for (i = 0; i < coin_val; ++i)
	{
		scanf("%d", &coins[i]);
	}
	
	coinSort(coins, coin_val);
	ans = dp_coin(value, coins, coin_val);
	
	printf("%d\n", ans);
	
  finallize:
	free(coins);
	return 0;
}

void coinSort(int* coins, const int count)
{
	int i, j, tmp_swap;
	
	for(i = count - 1; i >= 0; --i) {
		for(j = 0; j < i; ++j) {
			if(coins[j] > coins[j + 1]) {
				coins[j] =  coins[j] + coins[j + 1];
				coins[j + 1] = coins[j] - coins[j + 1];
				coins[j] = coins[j] - coins[j + 1];
			}
		}
	}
}
int dp_coin(const int target, const int* coins, const int coinCount)
{
	int currentValue;
	int mtx[target + 1];
	int i;
	
	for(i = 1; i <= target ; ++i) {
		mtx[i] = 99999;
	}
	mtx[0] = 0;
	
	for(i = 0; i < coinCount; ++i) {
		for(currentValue = 0; currentValue <= target - coins[i]; ++currentValue) {
			if (mtx[currentValue] + 1 < mtx[currentValue + coins[i]]) {
				mtx[currentValue + coins[i]] = mtx[currentValue] + 1;
			}
		}
	}
	
	return mtx[target];
}

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

int main() {
  int N,Y;
  cin>>N>>Y;
  for(int i=0;i<=N;i++){
    for(int j=0;j<=N-i;j++){
    	if(10000*i+5000*j+1000*(N-i-j)==Y){
          cout<<i<<" "<<j<<" "<<N-i-j<<endl;
        	return 0;
        }
    }
  }
  cout<<-1<<" "<<-1<<" "<<-1<<endl;
}
  

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

dp = [0] + [-1] * W
for i in range(1, N + 1):
    w, v = map(int, input().split())
    for sum_w in range(W - w, -1, -1):
        if dp[sum_w] >= 0:
            dp[sum_w + w] = max(dp[sum_w + w], dp[sum_w] + v)
    # print(dp)
print(max(dp))


Measured memory_bytes: 42392
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
#define PRINT(v) for (auto x : (v)) cout <<x <<" " ; cout <<endl;
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using mat = vector<vector<ll>>;
const ll MOD = 1000000007;
const ll INF = 10000000000000000;
const int inf = 1001001001;
vector<int> x4 = {0, 1, 0, -1}, x8 = {0, 1, 1, 1, 0, -1, -1, -1};
vector<int> y4 = {1, 0, -1, 0}, y8 = {1, 1, 0, -1, -1, -1, 0, 1};
template<class T> inline bool chmin(T& a, T b){if (a>b){a = b; return true;}return false;}
template<class T> inline bool chmax(T& a, T b){if (a<b){a = b; return true;}return false;}
template<class T> inline T powerM(T a,T b){if (b==0) return 1;
T tmp = powerM(a,b/2); if (b%2==0) return tmp*tmp%MOD; else return tmp*tmp%MOD*a%MOD; }
template<class T> inline T power(T a,T b,T m){ if (b==0) return 1;
  T tmp = power(a,b/2,m); if (b%2==0) return tmp*tmp%m; else return tmp*tmp%m*a%m; }
template<class T> inline T gcd(T a, T b){if (b==0) return a; return gcd(b, a%b);}
template<class T> inline T lcm(T a, T b){return a / gcd(a,b) * b;}
// ax+by=gcd(a,b)を解く
template<class T> inline T extgcd(T a,T b,T &x,T &y){if (b==0){x=1; y=0; return a;} T d=extgcd(b,a%b,y,x); y -= a/b*x; return d;}
void hey(){ cout <<"hey" <<endl; }

template<class T> struct edge { int to; T cost;};


int H,W;
vector<string> field;
vector<vector<int>> dp;

int main() {
  ll x,y; cin >>x >>y;
  ll res = abs(x-y);
  cout <<(res >= 2 ? "Alice" : "Brown") <<endl;
}


/*
0 0 lose
0 1 lose
0 2 win
1 1 lose
0 3 win
1 2 lose
0 4 win
1 3 win
2 2 lose
0 5 win
1 4 win
2 3 lose
// 差が1以下ならまけ、2以上ならかち

*/

Measured memory_bytes: 256
fst = int(input())
lists = []
for i in range(fst):
    lists.append(int(input()))

maxv = -10 ** 9
minv = lists[0]
leng = len(lists)
for j in range(1, leng) :
    maxv = max(maxv, lists[j] - minv)
    minv = min(minv, lists[j])

print(maxv) 


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

int main() {
  string s;
  cin >> s;
  int posa, posz;
  
  for (int i = 0; i < s.size(); i++) {
    if (s.at(i) == 'A') {
      posa = i;
      break;
    }
  }
  for (int i = s.size() - 1; i >= 0; i--) {
    if (s.at(i) =='Z') {
      posz = i;
      break;
    }
  }
  cout << posz - posa + 1 << endl;
}

Measured memory_bytes: 3700
fun main(args: Array<String>) {
    val a = readLine()!!.toInt()

    val b = (a.toDouble() / 1.08).toInt()
    when(a){
        (b * 1.08).toInt() -> println(b.toInt())
        ((b+1) * 1.08).toInt() -> println((b+1).toInt())
        else -> println(":(")
    }
}

Measured memory_bytes: 31764
using System;

public class Class1
{
	public static void Main(string[] args)
	{

        //Console.Write((int)'a');

        string S = Console.ReadLine();

        do
        {

            S = S.Remove(S.Length-1, 1);
            S = S.Remove(S.Length - 1, 1);

            //Console.WriteLine(S);

        } while (Judge(S) == false);



        Console.WriteLine(S.Length);


	}



    private static bool Judge(string S)
    {
        //Console.WriteLine((S.Length / 2).ToString() + " " + (S.Length - 1).ToString());
        string s1 = S.Substring(0, S.Length / 2);
        string s2 = S.Substring(S.Length / 2);

        

        bool even = true;
        
            if(s1 != s2)
            {
                even = false;
            }
       

        return even;

    }
}


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


def readstr():
    return input().strip()


def readint():
    return int(input())


def readnums():
    return map(int, input().split())


def readstrs():
    return input().split()


def main():
    S = readstr()
    T = readstr()

    sl = dict()
    tl = dict()
    for s, t in zip(S, T):
        if s not in sl:
            sl[s] = t
        else:
            if sl[s] != t:
                print('No')
                break

        if t not in tl:
            tl[t] = s
        else:
            if tl[t] != s:
                print('No')
                break
    else:
        print('Yes')


if __name__ == "__main__":
    main()


Measured memory_bytes: 3632
// JOI 2012-2013 予選5
#include<algorithm>
#include<iostream>

typedef long long ll;

int N, K;
ll X1[50], Y1[50], D1[50];
ll X2[50], Y2[50], D2[50];
ll xs[100], ys[100], ds[100];
int xl, yl, dl;

int main()
{
	std::cin >> N >> K;
	for( int i = 0; i != N; ++i )
	{
		std::cin >> X1[i] >> Y1[i] >> D1[i] >> X2[i] >> Y2[i] >> D2[i];
		
		xs[xl++] = X1[i]; ys[yl++] = Y1[i]; ds[dl++] = D1[i];
		xs[xl++] = X2[i]; ys[yl++] = Y2[i]; ds[dl++] = D2[i];
	}

	std::sort( xs, xs + xl ); std::sort( ys, ys + yl ); std::sort( ds, ds + dl );

	ll ans = 0;
	for( int a = 0; a != xl - 1; ++a )
	{
		for( int b = 0; b != yl - 1; ++b )
		{
			for( int c = 0; c != dl - 1; ++c )
			{
				int cnt = 0;
				for( int i = 0; i != N; ++i )
				{
					if( X1[i] <= xs[a] && xs[a + 1] <= X2[i] 
					 && Y1[i] <= ys[b] && ys[b + 1] <= Y2[i] 
					 && D1[i] <= ds[c] && ds[c + 1] <= D2[i] )
						++cnt;
				}

				if( cnt >= K )
					ans += ( xs[a + 1] - xs[a] ) * ( ys[b + 1] - ys[b] ) * ( ds[c + 1] - ds[c] );
			}
		}
	}

	std::cout << ans << std::endl;

	return 0;
}

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

int main(){
  char S[4];
  string ans;
  cin >> S;
  sort(S, S + 4);
  if(S[0] == S[1] && S[1] != S[2] && S[2] == S[3]){
    ans = "Yes";
  } else {
    ans = "No";
  }
  
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
# include "iostream"
# include "cstdio"
# include "queue"

using namespace std;

const int maxm=1e3+10;
const int Inf=0x3f3f3f3f;

int N,S,T,head[maxm],tot=1;
int A[maxm],B[maxm],C[maxm],D[maxm];
int Deep[maxm];

struct edge{
    int To;
    int Next;
    int Value;
    # define To(x) Edge[x].To
    # define Next(x) Edge[x].Next
    # define Value(x) Edge[x].Value
}Edge[maxm<<6];

inline void Add_Edge(int From,int To,int Value){Edge[++tot]=(edge){To,head[From],Value},head[From]=tot;return;}
inline void Insert_Edge(int From,int To,int Value){Add_Edge(From,To,Value);Add_Edge(To,From,0);return;}

inline bool Bfs(int S,int T){
	register int i,x;
	for(i=1;i<=N;i++) Deep[i]=0;
	queue<int> q;
	q.push(S);
	Deep[S]=1;
	while(q.size()){
		x=q.front(),q.pop();
		for(i=head[x];i;i=Next(i)){
			if(Value(i) && !Deep[To(i)]){
				Deep[To(i)]=Deep[x]+1;
				q.push(To(i));
				if(To(i)==T) return true;
			}
		}
	}
	return false;
}

int Dfs(int now,int Now){
	if(now==T) return Now;
	int Rest=Now,Reduce;
	for(int i=head[now];i;i=Next(i)){
		if(Value(i) && Deep[To(i)]==Deep[now]+1){
			Reduce=Dfs(To(i),min(Rest,Value(i)));
			if(Reduce==0) Deep[To(i)]=0;
			Value(i)-=Reduce;
			Value(i^1)+=Reduce;
			Rest-=Reduce;
		}
	}
	return Now-Rest;
}

int main(){
	register int i,j,Now,Ans=0;
	scanf("%d",&N);
	S=(N<<1)+1,T=(N<<1)+2;
	for(i=1;i<=N;i++) scanf("%d%d",A+i,B+i),Insert_Edge(S,i,1);
	for(i=1;i<=N;i++) scanf("%d%d",C+i,D+i),Insert_Edge(i+N,T,1);
	for(i=1;i<=N;i++){
		for(j=1;j<=N;j++){
			if(A[i]>C[j] || B[i]>D[j]) continue;
			Insert_Edge(i,j+N,1);
		}
	}
	N=(N<<1)+2;
	while(Bfs(S,T)){
		while(Now=Dfs(S,Inf)){
			Ans+=Now;
		}
	} 
	printf("%d",Ans);
	return 0;
} 

Measured memory_bytes: 384
#include <stdio.h>

using namespace std;

#define REP(a, i, n) for (int i = a; i < n; ++i)

int main() {
    char S[4];
    scanf("%s", S);

    int ans = 700;
    REP(0, i, 3) {
        if (S[i] == 'o') {
            ans += 100;
        }
    }

    printf("%d\n", ans);

    return 0;
}


Measured memory_bytes: 128
IDENTIFICATION                   DIVISION.
PROGRAM-ID.                      ABC_062_A.
ENVIRONMENT                      DIVISION.
DATA                             DIVISION.
WORKING-STORAGE                  SECTION.
    01 INP    PIC X(5).
    01 x      PIC 9(2).
    01 y      PIC 9(2).
PROCEDURE                        DIVISION.
MAIN.
    ACCEPT INP.

    UNSTRING INP
    DELIMITED BY SPACE
    INTO x y.

    IF x = 1 OR 3 OR 5 OR 7 OR 8 OR 10 OR 12 THEN
        IF y = 1 OR 3 OR 5 OR 7 OR 8 OR 10 OR 12 THEN
            DISPLAY "Yes"
        ELSE
            DISPLAY "No"
        END-IF
    ELSE
        IF x = 4 OR 6 OR 9 OR 11 THEN
            IF y = 4 OR 6 OR 9 OR 11 THEN
                DISPLAY "Yes"
            ELSE
                DISPLAY "No"
            END-IF
        ELSE
            IF y = 2 THEN
                DISPLAY "Yes"
            ELSE
                DISPLAY "No"
            END-IF
        END-IF
    END-IF.

    STOP RUN.


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

int main() {
	int k=0;
	int ans = 0;
	string S;
	cin >> S;
	int Slength = S.length();
	for (int i=0; i < Slength; i++) {
		if (S[i] == 'A' || S[i] == 'G' || S[i] == 'T' || S[i] == 'C') {
			k += 1;
			if (k > ans) ans = k;
		}
		else {
			k *= 0;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define sc scanf
#define pr printf
#define pb push_back
#define ll long long int
#define rp
//bruteforce to check prime
/*bool checkprime(ll j)
{
    if(j<=1)
        return false;
    else if(j==2)
        return true;
    else if(j%2==0)
        return false;
    else
    {
        bool prime=true;
        int divisor=3;
        int upperlimit=sqrt(j)+1;
        while(divisor<=upperlimit)
        {
            if(j%divisor==0)
                return false;
            divisor+=2;
        }
        return prime;
    }
}*/
int main()
{
  int n,i;
  cin>>n;
  bool q=false;
  for(i=1;i<=9;i++)
  {
      if(n%i==0 && 1<=n/i && n/i<=9)
      {
          q=true;
          continue;
      }
  }
  cout<<(q?"Yes":"No")<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<vector>
#include<string>
#include<iostream>
#include<iomanip>

using namespace std;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int N, A;
  double RES=0.0;
  
  cin>>N;
  cin.ignore(); //改行読み飛ばし
  for(int i=0;i<N;i++){
    cin>>A;
    RES+=(1.0/(double)A);
  }
  cout<<fixed<<setprecision(8)<<(1.0/RES)<<"\n";
  
  return 0;
}

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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
	return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value!=0>::type
fill_v(U &u,const V... v){u=U(v...);}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_v(U &u,const V... v){
	for(auto &e:u) fill_v<T>(e,v...);
}

int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int64 N;
	cin >> N;
	vector<int64> a(N);
	REP(i, N) { cin >> a[i]; a[i]--; }
	vector<int64> res;
	priority_queue<int64, vector<int64>, greater<int64>> pq;
	map<int64, set<int64>> cnt;
	vector<int64> in(N, 0);
	REP(i, N) {
	  in[a[i]]++;
	}
	REP(i, N) {
	  cnt[in[i]].insert(i);
	  pq.push(i);
	}
	vector<int64> used(N, 0);
	REP(i, N-3) {
	  if (cnt[N-i-1].size()) {
	    res.push_back(*(cnt[N-i-1].begin()));
	    used[res.back()] = 1;
	    break;
	  }
	  int64 p1 = pq.top(); pq.pop();
	  int64 p2 = pq.top(); pq.pop();
	  int64 use;
	  if (res.size() && a[res.back()] == p1) {
	    res.push_back(p2); used[p2] = 1;
	    pq.push(p1);
	    cnt[in[p2]].erase(p2);
	    use = p2;
	  } else {
	    res.push_back(p1); used[p1] = 1;
	    pq.push(p2);
	    cnt[in[p1]].erase(p1);
	    use = p1;
	  }
	  int64 tar = a[use];
	  cnt[in[tar]].erase(tar);
	  in[tar]--;
	  cnt[in[tar]].insert(tar);
//	  cout << res.back() << " ";
	}
//	cout << endl;
	deque<int64> ord;
	REP(i, N) {
	  if (!used[i]) ord.push_back(i);
	}
	if (res.size() && a[res.back()] == ord[0]) {
	  int64 x = ord[0]; ord.pop_front();
	  res.push_back(ord[0]); ord.pop_front();
	  ord.push_front(x);
	}
	do {
	  if (res.size() && a[res.back()] == ord[0]) continue;
	  bool out = 0;
	  REP(i, ord.size()-1) {
	    if (a[ord[i]] == ord[i+1]) {
	      out = 1;
	      break;
	    }
	  }
	  if (out) continue;
	  REP(i, ord.size()) {
	    res.push_back(ord[i]);
	  }
	  break;
	} while (next_permutation(all(ord)));
	if (res.size() < N) {
	  cout << -1 << endl;
	  return 0;
	}
	REP(i, res.size()) {
	  cout << res[i]+1 << " ";
	}
	cout << endl;
}


Measured memory_bytes: 16500
#include<iostream>
using namespace std;
int main() {
	int a[11],date[11];
	for (int i = 1; i <= 5; i++) {
		cin >> a[i];
	}
	int dai = -999999;
	int o;
	for (int i = 1; i <= 5; i++) {
		int dai = -999999;
		for (int z = 1; z <= 5; z++) {
			if (dai <= a[z]) {
				dai = a[z];
				o = z;
			}
		}
		date[i] = dai;
		a[o] = -9999999;
	}
	for (int i = 1; i <= 4; i++) {
		cout << date[i]<<" ";
	}
	cout << date[5] << endl;
}


Measured memory_bytes: 3104
#include <bits/stdc++.h>
typedef long long lint;
using namespace std;

int main() {
    lint n, d;
    cin >> n >> d;
    vector<lint> x(n), y(n);
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
    }
    int res = 0;
    for (int i = 0; i < n; i++) {
        if (x[i] * x[i] + y[i] * y[i] <= d * d) {
            res++;
        }
    }
    cout << res << endl;
}

Measured memory_bytes: 6420
object Main extends App {
  import scala.io.StdIn._

  val Array(n, a, b, c) = readLine.trim.split(' ').map(_.toInt)
  val lengths = Array.tabulate(n){_ ⇒ readInt()}
  println(
    (0 until (1 << (n * 2))).map(p ⇒ choice(p, n - 1, 0, 0, 0, 0)).min
  )
  def choice(pattern: Int, current: Int, forA: Int, forB: Int, forC: Int, usedMp: Int): Int = {
    if (current < 0) {
      if (forA * forB * forC == 0) Int.MaxValue
      else math.abs(forA - a) + math.abs(forB - b) + math.abs(forC - c) + usedMp
    }else {
      pattern % 4 match {
        case 0 ⇒ choice(pattern / 4, current - 1, forA, forB, forC, usedMp)
        case 1 if forA != 0 ⇒ choice(pattern / 4, current - 1, forA + lengths(current), forB, forC, usedMp + 10)
        case 1 ⇒ choice(pattern / 4, current - 1, lengths(current), forB, forC, usedMp)
        case 2 if forB != 0 ⇒ choice(pattern / 4, current - 1, forA, forB + lengths(current), forC, usedMp + 10)
        case 2 ⇒ choice(pattern / 4, current - 1, forA, lengths(current), forC, usedMp)
        case 3 if forC != 0 ⇒ choice(pattern / 4, current - 1, forA, forB, forC + lengths(current), usedMp + 10)
        case 3 ⇒ choice(pattern / 4, current - 1, forA, forB, lengths(current), usedMp)
        case _ ⇒ ???
      }
    }
  }
}

Measured memory_bytes: 29976
#include <bits/stdc++.h>
using namespace std;
int main(void){
    // Your code here!
    string s;
    int a=0,min=0;
    cin>>s;
    int n=s.length();
    for(int i=0;i<n;i++){
        if(s[i]=='S'){
            a++;
        }else{
            a--;
        }
        if(a<min){
            min=a;
        }
    }
    cout<<-min*2<<endl;
}


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

using ll = long long;
const int mod = 1e9+7;
int main(void){
    // Your code here!
    int n;
    cin >> n;
    long long a[n];
    for (int i=0; i<n; i++){
        cin >> a[i];
    }
    
    long long ans = 0;
    long long digit = 1;
    for (int i=0; i<60; i++){
        long long one = 0, zero = 0;
        for (int j=0; j<n; j++){
            if((1LL << i) & a[j]) one++;
            else zero++;
        }
        long long add = (one * zero) % mod * digit % mod;
        ans = (ans + add) % mod;
        digit = (digit * 2) % mod;
    }
    cout << ans << endl;
}


Measured memory_bytes: 5948
#include <bits/stdc++.h>
#define ll long long int
#define ld double
#define f first
#define s second
#define pb push_back
#define mk make_pair
#define MOD 1000000007
#define fo(i,a,b) for(i=a;i<b;i++)
#define foe(i,a,b) for(i=a;i<=b;i++)
#define boost ios::sync_with_stdio(false); cin.tie(0)
using namespace std;
int main()
{
	boost;
	int n;
	cin >> n;
	double ans;
	if(n % 2 == 0)
	ans = (ld)n / 2.0;
	else
	ans = (ld)(n + 1) / 2.0;
	ans /= (ld)n;
	cout << fixed << setprecision(10) << ans;
}


Measured memory_bytes: 256
import heapq
X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
Q = []
heapq.heappush(Q, (-A[0]-B[0]-C[0], 0, 0, 0))
for n in range(K):
    ans = heapq.heappop(Q)
    print(-ans[0])
    i, j, k = ans[1], ans[2], ans[3]
    if i < X-1:
        if (- A[i+1] - B[j] - C[k], i+1, j, k) not in Q:
            heapq.heappush(Q, (- A[i+1] - B[j] - C[k], i+1, j, k))
    if j < Y-1:
        if (- A[i] - B[j+1] - C[k], i, j+1, k) not in Q:
            heapq.heappush(Q, (- A[i] - B[j+1] - C[k], i, j+1, k))
    if k < Z-1:
        if (- A[i] - B[j] - C[k+1], i, j, k+1) not in Q:
            heapq.heappush(Q, (- A[i] - B[j] - C[k+1], i, j, k+1))

Measured memory_bytes: 3956
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
#include <cmath>
#include <stack>
#include <iomanip>
#include <tuple>
#include <functional>
#include <cfloat>
#include <map>
#include <stdio.h>
#include <string.h>
using ll = long long;

//LLONG_MAX
#define int long long
#define CONTAINS(v,n) (find((v).begin(), (v).end(), (n)) != (v).end())
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define ARY_SORT(a, size) sort((a), (a)+(size))
#define MAX(a,b) (((a) > (b)) ? (a) : (b))
#define MIN(a,b) (((a) < (b)) ? (a) : (b))
#define REMOVE(v,a) (v.erase(remove((v).begin(), (v).end(), (a)), (v).end()))
#define REVERSE(v) (reverse((v).begin(), (v).end()))
#define LOWER_BOUND(v,a) (lower_bound((v).begin(), (v).end(), (a)))
#define UPPER_BOUND(v,a) (upper_bound((v).begin(), (v).end(), (a)))
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define CONTAINS_MAP(m, a) (m).find((a)) != m.end()
using namespace std;

int N;
char S[50000];
int A[50000];

signed main()
{
	cin >> N;
	cin >> S;

	int ans = 0;
	for (int k = 0; k < N - 1; k++)
	{
		char* p = S + k;
		int len = N - k;

		int c = 0;
		A[0] = len;
		for (int i = 1; i < len; i++)
		{
			int off = (i - c);
			if (off < i && (off + A[off]) < A[c])
			{
				A[i] = A[off];
			}
			else
			{
				int j = (off >= i) ? 0 : MAX(0, (A[c] + c) - i);
				while (i + j < len && p[j] == p[i + j]) j++;
				A[i] = j;
				c = i;
			}
		}

		for (int i = 1; i < len; i++)
		{
			if (A[i] <= i)
			{
				ans = max(ans, A[i]);
			}
		}
	}

	cout << ans << endl;
	
}



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

int main()
{
	int n,i,b,a;
	cin>>n;
	cin>>a>>b;
	int f=0;
	for(i=a;i<=b;i++)
	{
		if(i%n==0)
		{
			f=1;
			break;
		}
	}
	if(f)
	cout<<"OK";
	else
	cout<<"NG";
	
	return 0;
}


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

#define lp(i,n) for(int i=0;i<n;i++)
#define lpin(a,i,n) for(int i=0;i<n;i++){cin>>a[i];}
using namespace std;

int main(){
  while(1){
    int x;
    cin>>x;
    if(x==0) break;
    int ans=0;
    for(int i=2;i<x;i++){
      int a=x;
      if(i%2==1){
	if(a%i==0){
	  a/=i;
	  if(a-((i-1)/2)>0){
	    ans++;
	  }
	}
      }
      else{
	if(a%(i/2)==0){
	  a/=i/2;
	  if(a%2==1) {
	    a/=2;
	    if(a-(i/2-1)>0)
	    ans++;
	  }
	}
      }
    }
    cout<<ans<<endl;
  }
  return 0;
}



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

int hs[100005];
int costos[100005];

int calc(int n){
    if(costos[n]!=-1){
        return costos[n];
    }
    return costos[n] = min(calc(n-2)+abs(hs[n]-hs[n-2]),calc(n-1)+abs(hs[n]-hs[n-1]));
}
int main(){
   int n,rta;
   scanf("%d", &n);
   for(int i=0; i<n; i++){
       scanf("%d", &hs[i]);
   }
   fill(begin(costos),end(costos),-1);
   costos[0] = 0;
   costos[1] = abs(hs[1]-hs[0]);
   rta = calc(n-1);
   printf("%d\n",rta);
   return 0; 
}

Measured memory_bytes: 4096
import java.util.Scanner;
class Main {

  public static void main(String args[]) {
Scanner sc=new Scanner(System.in);
int a=0;
while(sc.hasNext()) {
	String str=sc.next();
	//get char array from String
	char[] charArray = str.toCharArray();

	//process chars one by one
	for(int i=0; i < charArray.length; i++){

	    //if char is uppercase, make it lower case
	    if( Character.isUpperCase(charArray[i]) ){

	        charArray[i] = Character.toLowerCase( charArray[i] );

	    }else if(Character.isLowerCase(charArray[i]) ){

	        charArray[i] = Character.toUpperCase( charArray[i] );
	    }

	}

	//convert modified char array back to String
	str = new String(charArray);
if(a>0){
    System.out.print(" ");
}
	System.out.print(str);
	a+=1;
}
System.out.println();
sc.close();
  }


}



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

const int MAX_N = 10000;
bool ifnprime[MAX_N+1];

void set(){
    ifnprime[0] = ifnprime[1] = true;
    for(int i = 2; i*i <= MAX_N; i++){
        if( !ifnprime[i] ){
            int j = i*i;
            while( j <= MAX_N ){
                ifnprime[j] = true;
                j += i;
            }
        }
    }
}

int main(){
    int n,i,count;
    set();
    while( cin >> n ){
        count = 0;
        for(i=1;i<=n;i++){
            if( !ifnprime[i] && !ifnprime[n-i+1] ){
                count++;
            }
        }
        cout << count << endl;
    }
    return 0;
}

Measured memory_bytes: 1168
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <iomanip>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define repr(e,x) for(auto& e:x)
using namespace std;
typedef long long ll;

string S;
int a[26];
int b[26];

int main(){
    cin>>S;
    if(S=="zyxwvutsrqponmlkjihgfedcba"){
        cout<<-1<<endl;
        return 0;
    }

    string ans="";
    if(S.size()!=26){
        rep(i,S.size()) a[S[i]-'a']++;
        rep(i,26){
            if(a[i]==0){
                ans=S+(char)('a'+i);
                break;
            }
        }
    }else{
        rep(i,S.size()){
            a[i]=S[i]-'a';
            b[i]=S[i]-'a';
        }
        next_permutation(b,b+26);
        bool flag=true;
        rep(i,S.size()){
            if(flag){
                char c=b[i]+'a';
                ans+=c;
                if(a[i]!=b[i]){
                    flag=false;
                }
            }
        }
    }

    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define l_ength size
using ll = long long;
const int inf = 1000000;
const int mod = 1000000007;
using namespace std;

struct edge{
	int from;
	int to;
	int cost;
};

int main(){
	int n, m; cin >> n >> m;
	int dist[n][n];
	vector<edge> graph;
	for( int i = 0; i < n; ++i ){
		for( int j = 0; j < n; ++j ){
			dist[i][j] = ( i == j ) ? 0 : inf;
		}
	}
	for( int i = 0; i < m; ++i ){
		int a, b, c; cin >> a >> b >> c; --a; --b;
		dist[a][b] = dist[b][a] = c;
		graph.push_back( ( edge ){ a, b, c } );
	}
	for( int k = 0; k < n; ++k ){
		for( int i = 0; i < n; ++i ){
			for( int j = 0; j < n; ++j ){
				dist[i][j] = min( dist[i][j], dist[i][k]+dist[k][j] );
			}
		}
	}
	int ans = 0;
	for( auto e : graph ){
		bool flag = false;
		for( int i = 0; i < n; ++i ){
			for( int j = i+1; j < n; ++j ){
				// この条件は「i → j の最短距離に辺 e が使われる」と同値
				if( dist[i][e.from]+e.cost+dist[e.to][j] == dist[i][j] || dist[i][e.to]+e.cost+dist[e.from][j] == dist[i][j] ){
					flag = true;
				}
			}
		}
		if( !flag ) ++ans;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define yorn(f) cout<<((f)?"Yes":"No")<<endl
#define YORN(f) cout<<((f)?"YES":"NO")<<endl
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define println(x) cout << x << endl
using namespace std;
int main()
{
    int x, a, b;
    cin >> x >> a >> b;
    cout << (x - a) - (x -a) / b * b << endl;
    return 0;
}

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

int main() {
	ll a,b,c,d;
	cin>>a>>b>>c>>d;
	ll a1,a2,a3,a4;
	a1=a*c;a2=a*d;a3=b*c;a4=b*d;
	cout<<max(max(a1,a2),max(a3,a4));

	
	return 0;
}


Measured memory_bytes: 3628
import sys
d = input()

def rot_n(c):
    if 'a' <= c and c <= 'z':
        return chr((ord(c) - ord('a') + 1) % 26 + ord('a'))
    
    if 'A' <= c and c <= 'Z':
        return chr((ord(c) - ord('A') + 1) % 26 + ord('A'))
    
    return c
ans = rot_n(d)

print(ans)


Measured memory_bytes: 2940
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a;
		int b;
		a = sc.nextInt();
		b = sc.nextInt();
		System.out.println(Math.max(a+b, Math.max(a-b, a*b)));
	}
}


Measured memory_bytes: 21588
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
from collections import deque
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7
EPS = 1e-6
KETA = 10**7


def main():
    H, W, K = MAP()
    x1, y1, x2, y2 = LIST()
    c = [[-1] + [0 if c == "." else -1 for c in input()] + [-1]
         for i in range(H)]
    c = [[-1] * (W + 2)] + c + [[-1] * (W + 2)]
    c[x1][y1] = 0

    # 0123: 上下左右
    stack = deque([((x1 * KETA + y1) << 2) + 0, ((x1 * KETA + y1) << 2) + 1,
                   ((x1 * KETA + y1) << 2) + 2, ((x1 * KETA + y1) << 2) + 3])
    append, popleft = stack.append, stack.popleft
    DX = (1, 0, -1, 0)
    DY = (0, 1, 0, -1)
    while stack:
        b = popleft()
        d = b % 4
        x, y = divmod(b >> 2, KETA)
        flag = True
        a = c[x][y] + 1
        for k in range(1, K + 1):
            xx, yy = x + k * DX[d], y + k * DY[d]
            if c[xx][yy] == 0:
                append(((xx * KETA + yy) << 2) + (d - 1) % 4)
                append(((xx * KETA + yy) << 2) + (d + 1) % 4)
                c[xx][yy] = a
            elif c[xx][yy] != a:
                flag = False
                break
        if flag:
            append(((xx * KETA + yy) << 2) + d)
        if c[x2][y2] > 0:
            print(c[x2][y2])
            return

    print(-1)
    return


if __name__ == '__main__':
    main()


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

#define se second
#define fi first
#define mk(a,b) make_pair(a,b)
#define pb(a) push_back(a)

typedef pair<int,int> pii;
typedef pair<int,pii> pipii;

int X,K,Q;
int ans[100010];
vector<pipii> eve;
int O = -1;

int main()
{
    scanf("%d%d",&X,&K);
    for(int i = 0; i < K; i++)
    {
        int r;
        scanf("%d",&r);
        eve.pb(mk(r,mk(-1,-1)));
    }
    scanf("%d",&Q);
    for(int i = 0; i < Q; i++)
    {
        int t,a;
        scanf("%d%d",&t,&a);
        eve.pb(mk(t,mk(a,i)));
    }
    eve.pb(mk(0,mk(-1,-1)));
    sort(eve.begin(),eve.end());
    int MAX = X,MIN = 0,nl = 0,nu = X;
    for(int i = 1; i < eve.size(); i++)
    {
        pipii now = eve[i];
        int dif = now.fi - eve[i - 1].fi;
        if(O == -1)
        {
            nl -= dif;
            MIN += max(nl,0) - nl;
            nl = max(nl,0);
            nu -= dif;
            nu = max(nu,0);
        }
        else
        {
            nl += dif;
            nl = min(nl,X);
            nu += dif;
            MAX -= nu - min(nu,X);
            nu = min(nu,X);
        }
        if(now.se.fi == -1)O *= -1;
        else
        {
            if(nl == nu)ans[now.se.se] = nl;
            if(now.se.fi <= MIN)ans[now.se.se] = nl;
            else if(now.se.fi >= MAX)ans[now.se.se] = nu;
            else ans[now.se.se] = nl + now.se.fi - MIN;
        }
    }
    for(int i = 0; i < Q; i++)
    {
        printf("%d\n",ans[i]);
    }
    return 0;
}


Measured memory_bytes: 4980