akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;

public class Main {
    static long[] V;
    static long[] dp;

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(),k = sc.nextInt();
        V = new long[n + 1];
        dp = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            V[i] = sc.nextLong();
            dp[i] = Integer.MAX_VALUE;
        }
        long ans = solve(n,k);
        System.out.println(ans);
    }

    private static long solve(int n,int k) {
        dp[1] = 0;
        for (int j = 2; j <= n; j++) {
            for (int i = 1; i <= k; i++) {
                if (j-i >= 1)
                    dp[j] = Math.min(dp[j],dp[j-i] + Math.abs(V[j-i]-V[j]));
                else
                    break;
            }
        }
        return dp[n];
    }
}


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


  
int main(){
  

  int a,b,c,d,e,f,g,h;
  int sum1,sum2 =0;


  
  cin >> a >> b >> c >> d >> e >> f >> g >> h;


  sum1=e*a+f*b+(a/10)*g+(b/20)*h;
  sum2=e*c+f*d+(c/10)*g+(d/20)*h;

  
  



  if (sum1>sum2){
    cout << "hiroshi\n";
  }else if ( sum1<sum2){
    cout << "kenjiro\n";
  }else if (sum1==sum2){
    cout << "even\n";
  }
  
return 0;
}


Measured memory_bytes: 3076
#include <iostream>

using namespace std;

int group(int x) {
	if (x == 2) return 0;
	if (x == 4 || x == 6 || x == 9 || x == 11) return 1;
	return 2;
}

int main(int argc, char *argv[]) {
	int x, y;
	cin >> x >> y;
	if (group(x) == group(y)) printf("Yes\n");
	else printf("No\n");
	return 0;
}

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

int main() {
  int A, B;
  cin >> A >> B;
  if (A > 0) cout << "Positive" << endl;
  else if (A <= 0 && B >= 0) cout << "Zero" << endl;
  else if ((B - A + 1) % 2 == 0) cout << "Positive" << endl;
  else cout << "Negative" << endl;
}

Measured memory_bytes: 3596
/* Author : Harshit Jain a.k.a. iharshit009 */
#include <bits/stdc++.h>
#define vi               vector<int>
#define pb(x)            push_back(x)
#define all(x)           x.begin(), x.end()
#define sortall(x)       sort(all(x))
#define sortrev(x)       sort(all(x), greater<int>())
#define debug(x)         cout << '>' << #x << ':' << x << endl;
#define int              long long
#define ld               long double
#define endl 			 "\n";
#define mp 				 make_pair
#define pii 			 <int, int>
#define lb 				 lower_bound
#define ub				 upper_bound
#define len(a)           int((a).size())
#define prec(n)          fixed<<setprecision(n)
#define cnt(n)           __builtin_popcountll(n)
#define pi               pair<int, int>
const int mod = 1000000007;
using namespace std;
using namespace std::chrono;
const int N = 1e5 + 5; 
// int n;
int n;
int a[N];
int dp[N];
int func(int idx){
	if(idx == n-1) return 0;
	if(idx >= n) return INT_MAX;
	if(dp[idx] != -1) return dp[idx];
	return dp[idx] = min(abs(a[idx]- a[idx+1])+func(idx+1), abs(a[idx] - a[idx+2])+func(idx+2));
}






int32_t main(){
auto start = high_resolution_clock::now(); // starting clock
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int t;
t = 1;
// cin >>t;
while(t--){

memset(dp,-1,sizeof(dp));
cin >> n;
for(int i = 0; i<n; i++){
	cin >> a[i];
}

cout << func(0) << endl;




}
auto stop = high_resolution_clock::now(); // stop clock
auto duration = duration_cast<microseconds>(stop - start);  // printing duration
cerr << "Time taken by function: " << duration.count() << " milliseconds" << endl; 
return 0;
}

Measured memory_bytes: 7524
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=2e5;
int pre[maxn+5],last[maxn+5],other[maxn+5],vis[maxn+5],a[maxn+5],b[maxn+5];
int all=-1,n,m,flag=0,ans=0;

void build(int u,int v)
{
	pre[++all]=last[u];
	last[u]=all;
	other[all]=v;
}

 void dfs(int ds,int cnt)
 {

 	 if(cnt>2) return;
 	 if(ds==n&&cnt<=2) ans++;
 	 int dt,de;
 	 dt=last[ds];
 	 while(dt!=-1){
	 	 de=other[dt];
	 	 if(vis[de]==0)
		 {
		 	 vis[de]=1;
		 	 dfs(de,cnt+1);
		 }
		 dt=pre[dt];
	 }
 }

int main(){
	memset(last,-1,sizeof(last));
	scanf("%d %d",&n,&m);
	for(int i = 1;i <= m;i++){
		scanf("%d %d",&a[i],&b[i]);
		build(a[i],b[i]);
	}
	dfs(1,0);
	if(ans!=0) printf("POSSIBLE\n");
	else printf("IMPOSSIBLE\n");
}


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


int main(){
  
  int N;
  cin >> N;
  int A[100];
  for(int i = 0; i < N; i++)
    cin >> A[i];
  int alice = 0, bob = 0;
  
  sort(A,A+N,greater<int>());
  
  for(int i = 0; i < N; i++){
    if(i % 2 != 0){
       alice += A[i];
     }else{
      bob += A[i];
     }
  }

  if(alice > bob){
    cout << alice - bob << endl;
    }else{
      cout << bob - alice << endl;
    }

 return 0;
 
}



Measured memory_bytes: 256
from fractions import gcd

n = int(input())
A = list(map(int, input().split()))

left = [0]*n
right = [0]*n

for i in range(n-1):
    left[i+1] = gcd(left[i], A[i])
    right[n-i-2] = gcd(right[n-i-1], A[n-i-1])

ans = 0
for i in range(n):
    ans = max(ans, gcd(left[i], right[i]))
print(ans)


Measured memory_bytes: 89580
N,*A=map(int, open(0).read().split())
st=0
ans=1
for i,a in enumerate(A):
    if st==1:
        if A[i-1]>a:
            st=0
            ans+=1
    elif st==-1:
        if A[i-1]<a:
            st=0
            ans+=1
    elif st==0 and i!=0:
        p=A[i-1]
        if p<a:
            st=1
        elif p>a:
            st=-1
print(ans)

Measured memory_bytes: 14052
use io::*;

fn main() {
    let con = read_string();
    let mut sc = Scanner::new(&con);

    let n: i64 = sc.next();

    let mut ans = 0;
    for i in 1..n + 1 {
        if i % 2 == 0 {
            continue;
        }
        let mut cnt = 0;
        for j in 1..i + 1 {
            if i % j == 0 {
                cnt += 1;
            }
        }

        if cnt == 8 {
            ans += 1;
        }
    }

    println!("{}", ans);
}

pub mod io {
    use std;
    use std::str::FromStr;

    pub struct Scanner<'a> {
        iter: std::str::SplitWhitespace<'a>,
    }

    impl<'a> Scanner<'a> {
        pub fn new(s: &'a str) -> Scanner<'a> {
            Scanner {
                iter: s.split_whitespace(),
            }
        }

        pub fn next<T: FromStr>(&mut self) -> T {
            let s = self.iter.next().unwrap();
            if let Ok(v) = s.parse::<T>() {
                v
            } else {
                panic!("Parse error")
            }
        }

        pub fn next_vec_len<T: FromStr>(&mut self) -> Vec<T> {
            let n: usize = self.next();
            self.next_vec(n)
        }

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

    pub fn read_string() -> String {
        use std::io::Read;

        let mut s = String::new();
        std::io::stdin().read_to_string(&mut s).unwrap();
        s
    }

    pub fn read_line() -> String {
        let mut s = String::new();
        std::io::stdin().read_line(&mut s).unwrap();
        s.trim_right().to_owned()
    }
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
#define sqr(x) ((x)*(x))
using namespace std;
int n,m,a[15][15],ans;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&a[i][j]);
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++){
			int sum=0;
			for(int k=1;k<=m;k++)
				sum+=sqr(a[i][k]-a[j][k]);
			int t=(int)sqrt(sum);
			if(t*t==sum)ans++;
		}
	printf("%d",ans);
	return 0;
}

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

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

typedef long long ll;
using namespace std;
int mod = 1000000007;

int main(void){
    int A, B; cin >> A >> B;
    cout << max(A-2*B, 0) << endl;
    return 0;
}

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

int main(){
    int n,m,ansn,ansm;
    cin >> n >> m;
    if(n == 0 || n == 1) ansn = 0;
    else ansn = n*(n-1)/2;
    if(m == 0 || m == 1) ansm = 0;
    else ansm = m*(m-1)/2;
    cout << ansn + ansm << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
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];
    }
    for (int i=0; i<n; i++){
        v[i] -= c[i];
    }
    int res = 0;
    for (int i=0; i<n; i++){
        if(v[i] > 0){
            res += v[i];
        }
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		@SuppressWarnings("resource")
		Scanner sc = new Scanner(System.in);
		// ???????????????????????°
		int num = sc.nextInt();

		for (int i = 0; i < num; i++) {
			int[] inputNumList = new int[3];

			inputNumList[0] = sc.nextInt();
			inputNumList[1] = sc.nextInt();
			inputNumList[2] = sc.nextInt();

			// ?????????????????????inputNumList[2]?????§?????????????????£?????????
			Arrays.sort(inputNumList);

			if (inputNumList[0] * inputNumList[0] + inputNumList[1]
					* inputNumList[1] == inputNumList[2] * inputNumList[2]) {
				System.out.println("YES");

			} else {
				System.out.println("NO");
			}
		}

	}

}

Measured memory_bytes: 34476
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
namespace GeometryWithLongdouble {
	typedef long double ld;
	const ld eps = 1e-9;
	struct point {ld x, y; };
	struct line {point a, b; }; //Be sure that a and b are distinct.
	void ReadPointInt(point &a) {read(a.x), read(a.y); }
	void ReadLineInt(line &a) {ReadPointInt(a.a), ReadPointInt(a.b); }
	void CerrPoint(point a) {cerr << a.x << ' ' << a.y << endl; }
	void CerrLine(line a) {cerr << a.a.x << ' ' << a.a.y << ' ' << a.b.x << ' ' << a.b.y << endl; }
	point operator + (point a, point b) {return (point) {a.x + b.x, a.y + b.y}; }
	point operator - (point a, point b) {return (point) {a.x - b.x, a.y - b.y}; }
	point operator * (point a, ld b) {return (point) {a.x * b, a.y * b}; }
	ld dot(point a, point b) {return a.x * b.x + a.y * b.y; }
	ld operator * (point a, point b) {return a.x * b.y - a.y * b.x; }
	ld moo(point a) {return sqrtl(a.x * a.x + a.y * a.y); }
	ld dist(point a, point b) {return moo(a - b); }
	point unit(point a) {
		ld tmp = moo(a);
		assert(tmp > eps);
		return a * (1.0 / tmp);
	}
	point Projection(point x, line a) {
		ld d = dot(x - a.a, a.b - a.a) / dist(a.a, a.b);
		return a.a + unit(a.b - a.a) * d;
	}
	point Reflection(point x, line a) {
		return Projection(x, a) * 2 - x;
	}
	bool OnLine(point x, line a) {
		return fabsl((a.b - a.a) * (x - a.a)) <= eps;
	}
	bool OnSegment(point x, line a) {
		return dist(x, a.a) + dist(x, a.b) - dist(a.a, a.b) <= eps;
	}
	bool Parallel(line a, line b) {
		return fabsl((a.b - a.a) * (b.b - b.a)) <= eps;
	}
	bool Orthogonal(line a, line b) {
		return fabsl(dot(a.b - a.a, b.b - b.a)) <= eps;
	}
}
int main() {
	using namespace GeometryWithLongdouble;
	int q; read(q);
	while (q--) {
		line a, b;
		ReadLineInt(a);
		ReadLineInt(b);
		if (Parallel(a, b)) puts("2");
		else if (Orthogonal(a, b)) puts("1");
		else puts("0");
	}
	return 0;
}


Measured memory_bytes: 3104
#include <bits/stdc++.h>
using namespace std;
 
int main() {
int c;
c=0;
string S,T;
cin >> S >> T;
for(int i=0;i<S.size();i++){
    if(S.at(i)!=T.at(i)){
        c++; }
}
cout << c <<endl;
}

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

using namespace std;

int main(void) {

    constexpr long MOD = 1e9 + 7;

    auto inv = [&](long x) {
        long r = 1;
        long b = MOD-2;
        while(b) {
            if(b&1) r *= x, r %= MOD;
            x *= x, x %= MOD;
            b >>= 1;
        }
        return r;
    };
    auto comb = [&](long a, long b) {
        long r = 1;
        if(b < 0) return 0l;
        if(a < b) return 0l;
        for(long i=0; i<b; i++)
            r *= a - i, r %= MOD;
        for(long i=0; i<b; i++)
            r *= inv(i+1), r %= MOD;
        return r;
    };
    auto h = [&](long a, long b) {
        return comb(a+b-1, b-1);
    };

    long n, k;
    cin >> n >> k;

    for(long i=1; i<=k; i++) {
        long r = 1;
        r *= h(k-i, i), r %= MOD; // blue

        long t = comb(n-k+1, i);
        r *= t % MOD, r %= MOD; // red

        cout << r << endl;
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <cmath>
#define ll long long
#define out(a) printf("%d ",a);
using namespace std;
int n,h,l;
ll sum;
int hurt;
int ans=0;
int a[100050],b[100050];
int read()
{
	int s=0,t=1; char c;
	while (c<'0'||c>'9') {if (c=='-') t=-1; c=getchar();}
	while (c>='0'&&c<='9') {s=s*10+c-'0'; c=getchar();}
	return s*t;
}
int main()
{
	n=read(); h=read();
	for (int i=1;i<=n;i++) {
	  a[i]=read(),b[i]=read();
    }
    sort(b+1,b+n+1);
    sort(a+1,a+n+1);
    hurt=a[n];
    for (int i=n;i>=1;i--) {
      if (hurt>b[i]) {
      	l=n-i;
	    break;
	  }
	  sum+=b[i]; 
      if (sum>=h) {
      	out(n-i+1);
      	return 0;
      }
     }
     if (l==0) l=n;
     //printf("%d %d\n",sum,l);
    h-=sum;
    if (h%hurt==0) ans=h/hurt;
    else ans=h/hurt+1;
    ans+=l;
    out(ans);
    return 0;
}

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

using namespace std;

#define INF 1000000007
#define LINF (1LL << 61)
#define PI 3.14159265358979

typedef long long i64;
typedef pair<i64,i64> P;

inline i64 mod(i64 a, i64 m) { return (a % m + m) % m; }

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

i64 ceil(i64 a, i64 b) { return (a+b-1)/b; }
mt19937 rnd(time(NULL));

int d, c[30], s[404][30];
int ans[400];
clock_t start;
void solve(){
	start = clock();
	
	cin >> d;
	for(int i = 0; i < 26; i++) cin >> c[i];
	for(int i = 0; i < d; i++){
		for(int j = 0; j < 26; j++) cin >> s[i][j];
	}
	
	int ma = -INF;
	int lp = 0;
	while(clock()-start < 1.9*CLOCKS_PER_SEC){
		int cnt = 0;
		int la[26] = {};
		int res[400] = {};
		fill(la,la+26,-1);
		for(int i = 0; i < d; i++){
			int r = rnd() % 26;
			res[i] = r;
			cnt += s[i][r];
			la[r] = i;
			for(int j = 0; j < 26; j++){
				cnt -= c[j]*(i-la[j]);
			}
		}
		if(chmax(ma,cnt)){
			for(int i = 0; i < d; i++){
				ans[i] = res[i];
			}
		}
		lp++;
	}
	//cout << lp << endl;
	
	for(int i = 0; i < d; i++){
		cout << ans[i]+1 << endl;
	}
}

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

Measured memory_bytes: 3708
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<list>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<queue>

using namespace std;

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

#define PRINT(str) printf(#str "\n")
#define yOUT PRINT(Yes)
#define nOUT PRINT(No)
#define YOUT PRINT(YES)
#define NOUT PRINT(NO)
 
#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()

int main(){
	int n, MAX = 0, sum=0, inp;
	cin >> n;
	REP(i, n){
		cin >> inp;
		sum += inp;
		MAX = max(MAX, inp);
	}
	if(MAX < sum-MAX) yOUT;
	else nOUT;
}


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


#define sz(x) x.size()
using namespace std;


const int maxn = 100010;

int fat[maxn], rnk[maxn];
vector <int> vec[maxn];

int find(int x){
    if(fat[x] == x) return x;
    return fat[x] = find(fat[x]);
}

void unit(int x,int y){
    x = find(x);
    y = find(y);
    if(x == y) return;

    if(rnk[x]>rnk[y]) swap(x,y);
    if(rnk[x] == rnk[y]) rnk[y]++;
    fat[x] = y;
}



int main(){

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

    for(int i = 0; i < n; i++){
        fat[i] = i;
        rnk[i] = 0;
    }
    for(int i = 0; i < n; i++){
        int t;
        scanf("%d", &t);
        for(int j = 0; j < t; j++){
            int ax;
            scanf("%d", &ax);
            vec[ax].push_back(i);
        }
    }

    for(int i = 1; i <= m; i++){
        int siz = sz(vec[i]);
        for(int j = 0; j < (siz - 1); j++){
            unit(vec[i][j],vec[i][j+1]);
        }
    }
    int resp = find(0);
    int ok = 1;
    for(int i = 1; i < n; i++){
        if(resp != find(i)) ok = 0;
    }
    if(ok) puts("YES");
    else puts("NO");

}


Measured memory_bytes: 4736
use List::Util qw(max);
use List::Util qw(min);
my $input = <STDIN>;
chomp $input;
my ($N, $M, $X, $Y) = split / /, $input;
$input = <STDIN>;
chomp $input;
my @x = split / /, $input;
$input = <STDIN>;
chomp $input;
my @y = split / /, $input;
push(@x, $X);
push(@y, $Y);
my $max = max @x;
my $min = min @y;
if ($max < $min) {
  print "No War\n";
} else {
  print "War\n";
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define mem(s,t) memset(s,t,sizeof(s))
#define pb(s) push_back(s)
#define inf 0x3f3f3f3f
#define mn 100010
typedef long long ll;
using namespace std;

int main()
{
    int h,w,i,j,ansi,ansj;
    string s;
    cin>>h>>w;
    for (i=1;i<=h;i++)
    for (j=0;j<w;j++)
    {
        cin>>s;
        if (s=="snuke")
        {
            ansi=i;
            ansj=j;
        }
    }
    cout<<char('A'+ansj)<<ansi<<endl;
    return 0;
}



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

int main() {
  int H, W;
  cin >> H >> W;
  vector<vector<char>> a(H, vector<char>(W));
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++)
      cin >> a.at(i).at(j);
  }
  int h = 0, w = 0;
 
    for(int i = 0; i < H - h; i++){
      int T = 1;
      for(int j = 0; j < W; j++){
        if(a.at(i).at(j) == '.')
          T *= 1;
        else
          T *= 0;
      }
      if(T == 1){
        h++;
        for(int k = i; k < (H - 1); k++){
          for(int j = 0; j < W; j++){
            a.at(k).at(j) = a.at(k + 1).at(j);
          }
        }
        for(int j = 0; j < W; j++)
          a.at(H - 1).at(j) = '.';
        i = i - 1;
      }
    }
    
    for(int i = 0; i < W - w; i++){
      int T = 1;
      for(int j = 0; j < H; j++){
        if(a.at(j).at(i) == '.')
          T *= 1;
        else
          T *= 0;
      }
      if(T == 1){
        w++;
        for(int k = i; k < (W - 1); k++){
          for(int j = 0; j < H; j++){
            a.at(j).at(k) = a.at(j).at(k + 1);
          }
        }
        for(int j = 0; j < H; j++)
           a.at(j).at(W - 1) = '.';
        i = i - 1;
      }
    }
  
  for(int i = 0; i < (H - h); i++){
    for(int j = 0; j < (W - w); j++){
      cout << a.at(i).at(j);
      if(j == (W - w - 1))
        cout << endl;
    }
  }
}


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

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

int main(){
	int n;
	cin >> n;
	for(int i=1; i<=50000; i++){
		if(n==(int)(i*1.08)){
			cout << i << endl;
			return 0;
		}
	}
	cout << ":(" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <cmath>
#include <map>
#include <iomanip>
#include <unordered_map>
#include <stack>
#include <cstring>
#include <cctype>
#include <random>

using namespace std;
typedef long long  ll;
const ll INF = 1000000007;
const ll mod = 1000000007;
#define rep(i, n) for (int i = 0; i < (n); ++i)


vector<ll> a;



int main() {
	ll n;
	cin >> n;
	a = vector<ll>(n);
	rep(i, n) {
		cin >> a[i];
	}
	ll money = 1000;
	ll stock = 0;
	rep(i, n - 1) {
		if (a[i] >= a[i + 1]) {
			money += stock * a[i];
			stock = 0;
			continue;
		}
		else {
			stock += money / a[i];
			money -= a[i] * (ll)(money / a[i]);
		}
	}
	money += a[n - 1] * stock;
	cout << money << endl;
	return 0;
}

Measured memory_bytes: 3572
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<climits>
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<map>
#include<set>

using  ll = long long;
using ull = unsigned long long;
using namespace std;
#define pb push_back
int dy[]={0, 0, 1, -1, 1, 1, -1, -1};
int dx[]={1, -1, 0, 0, 1, -1, -1, 1};
constexpr ll kINF = 1152921504606846976;//2^60
constexpr double kEPS = 1e-6;

#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 rep(i,n) REP(i,n)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep(i,n) RREP(i,n)
#define mp make_pair
#define fi first
#define sc second

ll N;
ll a[3][100010];
ll dp[100010][3];

template<class T>bool chmax(T &a, T b) {if (a < b) {a = b; return true;} return false;}

int main(void) {
  cin >> N;

  rep(i,N) cin >> a[0][i] >> a[1][i] >> a[2][i];

  rep(i,N) {
    rep(j,3) {
      rep(k,3) {
        if (j == k)continue;
        chmax(dp[i + 1][k],dp[i][j] + a[k][i]);
      }
    }
  }

  cout << max(dp[N][0], max(dp[N][1],dp[N][2])) << endl;

  return 0;
}

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

using namespace std;
#define REPP(i,a,b,c) for(int i=a; i<=b; i+=c)
#define REP(i,a,b) REPP(i,a,b,1)
#define REVV(i,a,b,c) for(int i=a; i>=b; i-=c)
#define REV(i,a,b) REVV(i,a,b,1)
#define FOR(i,a) REP(i,0,(int)a-1)
#define FORD(i,a) REV(i,(int)a-1,0)
#define PB push_back
#define POB pop_back
#define MP make_pair
#define FI first
#define SE second
typedef long long ll;
typedef unsigned long long ull;
typedef pair < int , int > pii;
typedef vector < int > vi;
typedef vector < pii > vii;
typedef vector < ll > vl;

const double EPS = 1e-9;
const double PI = acos(-1);
const int INF = 1e9;
const ll MOD = 1e9 + 7;

ll addMod(ll a, ll b){
	return (a+b) % MOD;
}

ll mulMod(ll a, ll b){
	return (a*b) % MOD;
}

/////////////////////////////////////////////////////////

string str;

void solve(){
	bool flag = true;
	FOR(i,str.length()){
		if(flag){
			cout << str[i];
			flag = false;
		}
		if(str[i] == ' '){
			flag = true;
		}
	}
	cout << endl;
}

int main(){
	ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	getline(cin, str);
	solve();
	return 0;
}

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














int N, X[101], M, A[101];
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N;
	rep(i, 0, N) cin >> X[i];
	cin >> M;
	rep(i, 0, M) cin >> A[i];

	rep(i, 0, M) {
		int a = A[i] - 1;
		if (a == N - 1) {
			if (X[a] < 2019) X[a]++;
		}
		else {
			if (X[a] + 1 < X[a + 1]) X[a]++;
		}
	}

	rep(i, 0, N) cout << X[i] << endl;
}



Measured memory_bytes: 3204
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
using namespace std;
#define int long long


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

    string s; cin >> s;
    int n = s.size();
    vector<int> bcount(n);
    int ans = 0;

    if(s.at(0) == 'B') bcount.at(0) = 1;

    for(int i = 1;i < n;i ++){
        if(s.at(i) == 'B'){
            bcount.at(i) = bcount.at(i-1) +1;
        }else{
            bcount.at(i) = bcount.at(i-1);
        }
    }

    for(int i = 0;i < n;i ++){
        if(s.at(i) == 'W') ans += bcount.at(i);
    }

    cout << ans << endl;
}


Measured memory_bytes: 2196
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; --i)
#define whole(x) (x).begin(),(x).end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
using P = pair<int, int>;
#define debug(var) cerr << "[" << #var << "] " << var << endl
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
const ll mod = 1000000007;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,-1,0,1};


int main(){
    int r, g;
    cin >> r >> g;
    int ans = 2*g-r;
    
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3536
#include <cassert>
#include "limits.h"
#include <limits>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <complex>
#include <chrono>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#include <random>
#include <memory>
#include <utility>
 
#define rep(i, a, b) for (long long (i) = (a); i < (b); i++)
#define all(i) i.begin(), i.end()
#define debug(...) std::cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

void debug_out(){std::cerr<<std::endl;}

template<typename H,typename... T>
void debug_out(H head,T... tail){
  std::cerr<<" "<<head;
  debug_out(tail...);
}

 
template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, std::pair<T1, T2> pa) {
  return os << pa.first << " " << pa.second;
}
 
template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
  for (int i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
  return os;
}
 
template<typename T1,typename T2>
inline bool chmax(T1& a,T2 b){return a<b && (a=b,true);}
 
template<typename T1,typename T2>
inline bool chmin(T1& a,T2 b){return a>b && (a=b,true);}
 
long long pow_mod(long long a, long long b, long long mod=-1) {
  if ((a == 0)||(mod!=-1&&a%mod==0))return 0;
  long long x = 1;
  while (b > 0) {
    if (b & 1)x = (mod!=-1)?(x * a) % mod:x*a;
    a = (mod!=-1)?(a * a) % mod:a*a;
    b >>= 1;
  }
  return x;
}
 
// const long long MOD = 998244353;
const long long MOD = 1e9 + 7;

using ll = long long;
using P = std::pair<long long,long long>;

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

  ll n,k;
  std::cin>>n>>k;

  ll ans=0;
  std::vector<std::vector<ll>> graph(n);

  rep(i,0,n){
    ll a;
    std::cin>>a;
    a--;
    if(i==0){
      if(a!=0)ans++;  
    }else{
      graph[a].push_back(i);
    }
  }

  auto dfs=[&](auto f,ll now,ll par)->ll{
    ll ret=0;

    for(ll e:graph[now]){
      chmax(ret,f(f,e,now)+1);
    }

    if(ret==k-1&&par!=0){
      ans++;
      return -1;
    }

    return ret;
  };

  dfs(dfs,0,0);

  std::cout<<ans<<"\n";

  return 0;
}

Measured memory_bytes: 9600
a, b, c, x, y = map(int, input().split())
if 2*c>=a+b:
    print(a*x+b*y)
else:
    ans = min(x, y)*2*c
    if x>y:
        ans += min(a, 2*c)*(x-y)
    elif x<y:
        ans += min(b, 2*c)*(y-x)
    print(ans)

Measured memory_bytes: 3060
#Lupin The 4th: O(2^n)
def f(a, b, visited):
    w = W[visited] * 20
    return float(abs(lengths[a] - lengths[b])) / (2000.0 / (70 + w))

def solve():
    cache = dict([((i, 0), (0, [i])) for i in xrange(n)])
    def dfs(top, visited):
        if (top, visited) in cache:
            return cache[(top, visited)]
        ret = (1 << 30, [-1])
        for i in xrange(n):
            if (visited >> i) & 1 == 1:
                tmp = dfs(i, visited ^ (1 << i))
                c = tmp[0] + f(top, i, visited)
                if c < ret[0]:
                    ret = (c, tmp[1])
        cache[(top, visited)] = (ret[0], ret[1] + [top])
        return cache[(top, visited)]
    mask = (1 << n) - 1
    ret = (1 << 30, -1)
    for i in xrange(n):
        ret = min(ret, dfs(i, mask ^ (1 << i)))
    return ret[1]

n = input()
num, lengths, weights = zip(*[map(int, raw_input().split()) for _ in xrange(n)])
W = [0] + [sum(weights[i] for i in xrange(n) if (b >> i) & 1 == 1)  
           for b in xrange(1, 1 << n)]
print " ".join(map(lambda i:str(num[i]), solve()))

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

int main(){
 ll a,b,c,d;
 cin >> a >> b >> c >> d;
 ll res1 = a*c, res2 = b*d, res3 = c*b, res4 = d*a;
 cout << max(res1,max(res2,max(res3,res4)));
 return 0;
}


Measured memory_bytes: 3632
/*
套路
有Alice和Bob的一定是%2然后判定的_(:з」∠)_
 */
#define R register
#define ll long long
#include <bits/stdc++.h>

using namespace std;

int n, a, b;
int main()
{
	scanf("%d%d%d", &n, &a, &b);
	if((b - a - 1) % 2) puts("Alice");
	else puts("Borys");
	return 0;
}

Measured memory_bytes: 256
a,b,c = gets.split.map(&:to_i)
x = gets.to_i

cnt = 0
while a >= b && cnt < x
  b *= 2
  cnt += 1
end
while b >= c && cnt < x
  c *= 2
  cnt += 1
end

if a < b && b < c
  puts "Yes"
else
  puts "No"
end

Measured memory_bytes: 14352
#include <bits//stdc++.h>
using namespace std;
#define rep(i,n,k) for(int i=n;i<k;i++)
#define int long long
#define F first 
#define S second
#define P make_pair 

signed main(void){
    int ans=0;
    int n,m,q,p;
    cin>>n>>m;
    if(n<4)
    ans+=4-n;
    if(m<4)
    ans+=4-m;
    ans=ans*100000;
    if(n*m==1)
    ans+=400000;
    cout<<ans<<endl;
    
    
    
}


Measured memory_bytes: 256
/*----------------by syr----------------*/
/*

         iii                  ii
     rBQBBBBBBE       BBR iBBBBQBBL     XBBBBBBQBBBBB
   iBBQJ    7BBB      BBsSBBr   BBQ      i      cBBB
  rBBU       iBBw     BBBQi     HBBi           KBBi
  BBH         BB5    iBBB       isL          wBB5
 GBB         iBBi    6BB                   iBBB
 BBQ         BQB     BBD                  QBBi
 BBB        BQB     iQBi                1BBv
 sBBg     wBBB      QBB               iBBB
  7BBBBBBBBBi       BBR              wBBBBBBBBBBBBB
     irvi           ii               ii    i i iii
                i5U
               BBB
               BB7
              1BB
      iPBBBBBKBBR    JBR1       rQBO   BR  UBQP  iBBQi
    7BBBGs7sXBBBi     QBBr     gBBE   rBB BB2BB7HBZQBB
   QBBi      sBQ       BBB   iBBB     SQBBR  BBBB  cBQ
  gBQ        BBg        BBB KBBi      MBBH   BBB   BBs
 iBBv       iBBi         QBBBL        BBR   pBB   iBB
 pBB        BBB         iBBBB        iBB    BBL   KBB
 MBB       BBBR        BBB JBBi      DBR   iBQ    BBL
 GBB     7BBBB2      PBBH   BBBi     BQr   DBB   iBB
  BQBXwgBBP BB7    1BBB      BBQ7   1BB    BBc   BBB
   2BBBBw   BB    EBBS        QBBi  HBa   iBB    BB7
*/
#include<bits/stdc++.h>

using namespace std;

#define PH push
#define MP make_pair
#define PB push_back
#define fst first
#define snd second
#define FOR(i, x, y) for(int i = (x); i < (y); ++i)
#define REP(i, x, y) for(int i = (x); i <= (y); ++i)
#define x0 x0123456789
#define y0 y0123456789
#define x1 x1234567890
#define y1 y1234567890
#define x2 x2345678901
#define y2 y2345678901
typedef double db;
typedef long long ll;
typedef long double ldb;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int INF = 1e9 + 7;
const int maxn = 2e5 + 5;

int n, a, b, c, d;
int dp[maxn];
char s[maxn];

bool move(int &x){
	if(s[x + 1] != '#'){
		++x;
		return true;
	}
	if(s[x + 2] != '#'){
		x += 2;
		return true;
	}
	return false;
}

int main(){
	scanf("%d%d%d%d%d", &n, &a, &b, &c, &d);
	scanf("%s", s);
	--a; --b; --c; --d;
	if(c > d){
		for(; a != c; ){
			//printf("%d %d\n", a, b);
			bool upd = false;
			if(a + 1 != b && a + 1 <= c && s[a + 1] != '#'){
				++a, upd = true;
			}
			else if(a + 2 != b && a + 2 <=c && s[a + 2] != '#'){
				a += 2, upd = true;
			}
			else if((a + 1 == b || a + 2 == b) && move(b))
				upd = true;
			if(!upd)
				break;
		}
		for(; b != d; ){
			bool upd = false;
			if(s[b + 1] != '#' && b + 1 <= d){
				++b, upd = true;
			}
			else if(s[b + 2] != '#' && b + 2 <= d){
				b += 2, upd = true;
			}
			if(!upd)
				break;
		}
	}
	else{
		for(; b != d; ){
			//printf("%d\n", b);
			bool upd = false;
			if(s[b + 1] != '#' && b + 1 <= d){
				++b, upd = true;
			}
			else if(s[b + 2] != '#' && b + 2 <= d){
				b += 2, upd = true;
			}
			if(!upd)
				break;
		}
		for(; a != c; ){
			bool upd = false;
			if(s[a + 1] != '#' && a + 1 <= c){
				++a, upd = true;
			}
			else if(s[a + 2] != '#' && a + 2 <= c){
				a += 2, upd = true;
			}
			if(!upd)
				break;
		}
	}
	if(a == c && b == d)
		puts("Yes");
	else
		puts("No");
	return 0;
}



Measured memory_bytes: 384
#include <vector>
#include <algorithm>
#include <vector>
#include <iostream>
#include <string>
#include <set>
#include <map>
#include <fstream>
using namespace std;

const int INF = 1e7;

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

	long long n, k;
	cin >> n >> k;
	vector<long long> dp(n, 0);
	dp[0] = k;
	for (int i = 1; i < n; ++i) {
		dp[i] = dp[i - 1] * (k - 1);
	}
	cout << dp[n - 1] << endl;

	return 0;
}



Measured memory_bytes: 256
"use strict"
const assert = require('assert');

function main(input) {
    let ret = check(input);
    console.log(ret);
}

function check(input) {
    let ans;
    let [k, s] = input.split("\n");
    k = parseInt(k);
    if (s.length <= k) {
        ans = s;
    } else if (s.length > k) {
        let sliceS = s.slice(0, k) + "...";
        ans = sliceS;
    }
    return ans;
}

var input;
input = require('fs').readFileSync('/dev/stdin', 'utf8');
main(input);

// check
// var answer;

// input = `7
// nikoandsolstice`;
// answer = `nikoand...`;
// assert.equal(check(input), answer);

// input = `40
// ferelibenterhominesidquodvoluntcredunt`;
// answer = `ferelibenterhominesidquodvoluntcredunt`;
// assert.equal(check(input), answer);


Measured memory_bytes: 29616
S = input()


while len(S)!=0:
    if S[-7:]=="dreamer":
        S=S[:-7]
    elif S[-6:]=="eraser":
        S=S[:-6]
    elif S[-5:]=="dream" or S[-5:]=="erase":
        S=S[:-5]
    else:
        break


if len(S)==0:
    print("YES")
else:
    print("NO")

Measured memory_bytes: 3316
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int INF = 0x7fffffff;
const int tINF = INF>>2;
const ll LINF = 0x7fffffffffffffff;
const ll tLINF = LINF>>2;
const int maxn = 1e5;
const int modn = 1e9+7;



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

	int a,b;
	cin>>a>>b;
	if (a<6) cout<<0<<endl;
	else if (a>=6 && a<=12) cout<<b/2<<endl;
	else cout<<b<<endl;

	return 0;
}


Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

class Main {

	public static void main(String[] args) {
		Set<Long> setA = new TreeSet<Long>();
		Set<Long> setB = new TreeSet<Long>();
		try (Scanner sc = new Scanner(System.in)){
			int times = sc.nextInt();
			for (int i=0; i<times; i++) setA.add(sc.nextLong());
			times = sc.nextInt();
			for (int i=0; i<times; i++) setB.add(sc.nextLong());
			ArrayList<Long>  a = new ArrayList<Long>(setB);
			for (int i=0; i<times; i++) {
				Long l = a.get(i);
				boolean check = setA.contains(l);
				if (check) setA.remove(l);  //重複した場合削除
			}
			a = new ArrayList<Long>(setA);
			for (int i=0; i<a.size(); i++) System.out.println(a.get(i));
		}
	}
}


Measured memory_bytes: 194788
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000007;

int main(){
	long long x;
	cin >> x;
	long long a = 1;
	long long sum = 0;
	while(sum < x){
		sum += a;
		a++;
	}
	cout << a - 1 << endl;
	return 0;
}



Measured memory_bytes: 256
def ALDS1_3D():
    s0, s1 = [], []
    for i, e in enumerate(input()):
        if e == '\\':
                s0.append(i)
        elif e == '/':
            if len(s0) > 0:
                j = s0.pop()
                s = i - j
                while len(s1) > 0 and j < s1[-1][0]:
                    s += s1[-1][1]
                    s1.pop()
                s1.append((j, s))

    ss = [s[1] for s in s1]
    print(sum(ss))
    print(len(ss), *ss)





if __name__ == '__main__':
    ALDS1_3D()

Measured memory_bytes: 8100
#include<iostream>
#include<iomanip>
#include<string>
#include<set>
#include<vector>
#include<utility>
#include<queue>
#include<algorithm>
#include<functional>
using namespace std;
#define LL long long
#define MOD 100000
#define inf 1999999999
#define ALL(x) (x).begin(), (x).end()
#define LBi(x, n) lower_bound(ALL(x), n) - (x).begin()
#define ZIP(x) (x).erase(unique(ALL(x)), (x).end())
#define Pi pair<int, int>
#define Vi vector<int>

#define rep(n) for(int i = 0; i < n; i++)

string s = "";
char ch[10];
int n, a, b, c, d, x, m[5];

int main() {
	cin >> n >> a >> b;
	cout << min(a * n, b) << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

int main() {
	ll n,m,a[3];
	cin>>n>>m;
	for(ll i=0;i<3;i++){
		a[i]=-1;
	}
	for(ll i=0;i<m;i++){
		ll x,y;
		cin>>x>>y;
		x--;
		if(a[x]!=-1&&a[x]!=y){
			cout << -1;
			return 0;
		}
		a[x]=y;
	}
	for(ll i=0;i<n;i++){
		if(a[0]==0&&n!=1){
			cout << -1;
			return 0;
		}
		if(a[i]==-1){
			if(i!=0){
			cout <<0;
			}
			else{
				if(n!=1){
				cout << 1;
				}
				else{
					cout << 0;
				}
			}
		}
		else{
			cout <<a[i];
		}
	}
	// your code goes here
	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define vi vector<int>
#define vb vector<bool>
#define lli long long int
#define vvi vector<vector<int>>
#define loop(n) for (int i = 0; i < n; i++)
using namespace std;

auto SpeedUp = []() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    return 0;
}();

int knapSack(vi &weg, vi &value, int n, int w,int tval, vector<vector<lli>> &dp)
{
    //dp[idx][val] = it will store the min weght to require to get this value;
    dp[0][0] = 0;
    for (int idx = 1; idx <= n; idx++)
    {
        dp[idx][0] = 0; // by not thaking any object thus obtaning 0 value;
        for (int val = 1; val <= tval; val++)
        {
            dp[idx][val] = dp[idx - 1][val]; //not taking current object;

            if (val >= value[idx-1])
                dp[idx][val] = min(dp[idx][val], dp[idx - 1][val - value[idx-1]] + weg[idx-1]);
        }
    }

    for (int val = tval; val >= 0; val--)
        if (dp[n][val] <= w)
            return val;
}

int solve()
{
    int n, w;
    cin >> n >> w;
    vi weg(n, 0), val(n, 0);
    int tval = 0;
    loop(n)
    {
        cin >> weg[i];
        cin >> val[i];
        tval += val[i];
    }

    vector<vector<lli>> dp(n + 1, vector<lli>(tval + 1, 1e9));
    return knapSack(weg, val, n, w, tval, dp);
}

int main()
{

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

Measured memory_bytes: 83192
#include<bits/stdc++.h>
using namespace std;
long gcd(long a,long b){
  if(a%b == 0)return b;
  else return gcd(b,a%b);
}

int main(){
  long a,b;
  cin >> a >> b;
  vector<int>p;
  int i,j;
  int chk = 0;
  p.push_back(2);
  for(i=3;i<=1000000;i+=2){
    chk = 1;
    for(j=0;j<p.size()&&sqrt(i)>=p[j];j++){
      if(i%p[j]==0){
        chk=0;
        break;
      }
    }
    if(chk==1)p.push_back(i);
  }
  long g = gcd(max(a,b),min(a,b));
  int ans = 1;
  for(j=0;j<p.size();j++){
    if(g%p[j]==0){
      ans++;
      while(g%p[j]==0)g/=p[j];
    }
  }
  if(g>p[p.size()-1])ans++;
  cout << ans;

}


Measured memory_bytes: 892
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>

int main(){

    int n; std::cin >> n;
    std::vector<int> a(n+1),b(n+1);

    for(int i = 1; i <= n;i++){
        std::cin >> a[i];
    }

    for(int i = n; i > 0;i--){

        int sumBall = 0;
        for(int k = i*2; k <= n; k += i){
            if(b[k] == 1){
                sumBall ++;
            }
        }

        if(sumBall % 2 != a[i]){
            b[i] = 1;
        }
    }

    std::vector<int> ans;
    for(int i = 1; i <= n;i++){
        if(b[i]) ans.emplace_back(i);
    }

    std::cout << ans.size() << std::endl;
    for(int i = 0; i < ans.size(); i ++){
        printf("%d%c", ans[i],ans.size()==i+1?'\n':' ' );
    }
    return 0;
}

Measured memory_bytes: 3064
#include <iostream>
#include <string>
using namespace std;
int main(int argc, char* argv[])
{
	string S;
	cin>>S;
	if (S[0]!='A'){
		cout<<"WA"<<endl;
		return 0;
	}
	int sLen=S.length();
	int i,CNum=0;
	for (i=1;i<sLen;i++){
		if (S[i]!='C' && (S[i]<'a' || S[i]>'z')){
			cout<<"WA"<<endl;
			return 0;
		}
	}
	for (i=2;i<=sLen-2;i++){
		if (S[i]=='C'){
			CNum++;
		}
		if (CNum==2){
			cout<<"WA"<<endl;
			return 0;
		}
	}
	if (CNum==1){
		cout<<"AC"<<endl;
	}else{
		cout<<"WA"<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#include <cmath> //sqrt pow
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
 
#define rep(i,n) for(int i = 0; i < n; i++)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define mod 1000000007
using ll = long long;
using namespace std;
int main(){
  int n;
  cin >> n;
  if(n == 1) cout << "Hello World" << endl;
  else{
    int a,b;
    cin >> a >> b;
    cout << a + b << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,k;
	cin>>n>>k;
	int a[n],i=0;
	for (i = 0; i < n; ++i)
	 {
	 	cin>>a[i];
	 } 
	int dp[k+1]={0};
	dp[0]=-1;
	for(i=0;i<=k;i++)
	{
		if(dp[i]==-1)
		{
			for(int j=0;j<n;j++)
			{
				if(i+a[j]<=k)dp[i+a[j]]=1; 
			}
		}
		else if(dp[i]==0)
		{
			int z=1;
			for(int j=0;j<n;j++)
			{
				if(i-a[j]<0) break;
				if(dp[i-a[j]]==-1){z=0;break;}
			}
			if(z==0)dp[i] = 1;
			else {
				dp[i] = -1;
				for(int j=0;j<n;j++)
				{
					if(i+a[j]<=k)dp[i+a[j]]=1; 
				}
			}
		}
	}
	// for(i=0;i<=k;i++) cout<<dp[i]<<" ";
	if(dp[k]==-1)cout<<"Second"<<endl;
	else cout<<"First"<<endl;
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
//using namespace __gnu_pbds;

const int N = 1e6 + 10;
const int MOD = 1e9 + 7;
const int64_t INF = 5e18;
const double PI = 2 * acos(0.0);
//template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int n, dp[N][2][2];

int fun(int pos, int zero, int nine) {
    if (pos == 0) {
        return (zero && nine);
    }
    int &tmp = dp[pos][zero][nine];
    if (tmp != -1) {
        return tmp;
    }
    tmp = 0;
    for (int i = 0; i < 10; i++) {
        tmp += fun(pos - 1, (i == 0) | zero, (i == 9) | nine);
        tmp %= MOD;
    }
    return tmp;
}

int main() {
//    ios::sync_with_stdio(false);
//    cin.tie(0);
    cin >> n;
    memset(dp, -1, sizeof dp);
    cout << fun(n, 0, 0) << '\n';
    return 0;
}


Measured memory_bytes: 81620
#include<stdio.h>

int main(void){
  int n;
  int flag = 0;
  scanf("%d", &n);

  for(int i = 9; i > 0; i--){
   if(n % i == 0 && n / i < 10){
    printf("Yes\n");
    flag = 1;
    break;
   }
  }
  if(flag == 0)
    printf("No\n");

  return 0;
}



Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <queue>
#include <set>
#include <cmath>
#include <map>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)

using namespace std;
typedef long long int lli;
//const int MAX=;

int main(){
	int D,N;
	cin>>D>>N;
	if(D==0){
		if(N==100){
			cout<<101;
		}
		else cout<<N;
	}
	else if(D==1){
		if(N==100){
			cout<<10100;
		}
		else cout<<N*100;
	}
	else{
		if(N==100){
			cout<<1010000;
		}
		else cout<<N*10000;
	}
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pii;
#define fi first
#define se second
#define mod 1000000007
#define ios ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
ll a[100005];
vector<ll> adj[100005];
int main()
{
	ios;
	ll n,m,j,i,u,v,f=0;
	bool b;
	cin>>n>>m;
	for(i=1;i<=n;i++)
		cin>>a[i];
	for(i=1;i<=m;i++)
	{
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for(i=1;i<=n;i++)
	{
		b=true;
		for(j=0;j<adj[i].size();j++)
		{
			if(a[i]<=a[adj[i][j]])
			{
				b=false;
				break;
			}
		}
		if(b)
			f++;		
	}
	cout<<f<<endl;
}


Measured memory_bytes: 10244
import java.util.Scanner;
public class Main
{
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    int N=sc.nextInt();
    double X=sc.nextDouble();
    int T=sc.nextInt();
    double a =N/X;
    double temp=Math.ceil(N/X);
    double ans=T*temp;
    int ans1=(int)ans;
    
    
    
    System.out.println(ans1);
  }}

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

int main(void)
{
    int N;
    cin >> N;

    string S;
    cin >> S;

    if (N % 2 == 1) {
        cout << "No" << endl;
        return 0;
    }
    else {
        if (S.substr(0, N/2) == S.substr(N/2, N)) {
            cout << "Yes" << endl;
            return 0;
        }
        else {
            cout << "No" << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 256