akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define maxn 300005
using namespace std;
int k,n;
int ans[maxn];
int main()
{
	scanf("%d%d",&k,&n);
	if(!(k&1))
	{
		printf("%d",k/2);
		for(int i=2;i<=n;i++)
			printf(" %d",k);
		return 0;
	}
	for(int i=1;i<=n;i++)
		ans[i]=(k+1)/2;

	int top=n;
	for(int i=1;i<=n/2;i++)
	{
		if(ans[top]==1)
			top--;
		else
		{
			ans[top]--;
			for(int i=top+1;i<=n;i++)
				ans[i]=k;
			top=n;
		}
	}
	for(int i=1;i<=top;i++)
		printf("%d ",ans[i]);
}


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

int descending_compare(const void *a, const void *b){
    if (*(int*)a > *(int*)b){
        return -1;
    }else if (*(int*)a == *(int*)b){
        return 0;
    }else{
        return 1;
    }
}

int ascending_compare(const void *a, const void *b){
    if (*(int*)a < *(int*)b){
        return -1;
    }else if (*(int*)a == *(int*)b){
        return 0;
    }else{
        return 1;
    }
}


int lower_bound(int *a, int n, int key){
    int left, mid, right;
    left = 0, right = n;
    mid = (left + right)/2;
    while ((left+1 != mid || mid+1 != right) && mid != left){
        if (key > a[mid]){
            left = mid;
        }else{
            right = mid+1;
        }
        mid = (left + right)/2;
    }
    if (a[left] >= key)return left;
    if (a[mid] >= key)return mid;
    if (a[right] >= key)return right;
    return n;
}

unsigned long  gcd(unsigned long x, unsigned long y)
{
        if (y == 0) {
                return x;
        } else {
                return gcd(y, x % y);
        }
}

int boat_from_1[200005] = {0};
int boat_to_n[200005] = {0};


int main(void){
    int n, m;
    int i;
    int j = 0;
    int k = 0;
    int a,b;
    scanf("%d %d", &n, &m);
    for (i = 0; i < m; i++){
        scanf("%d %d", &a, &b);
        if (a == 1){
            boat_from_1[j] = b;
            j++;
        }
        if (b == n){
            boat_to_n[k] = a;
            k++;
        }
    }
    qsort(boat_from_1, j, sizeof(int), ascending_compare);
    qsort(boat_to_n, k, sizeof(int), ascending_compare);

    for (i = 0; i < j; i++){
        if (bsearch(&boat_from_1[i], boat_to_n, k, sizeof(int), ascending_compare) != NULL){
            printf("POSSIBLE\n");
            return 0;
        }
    }

    printf("IMPOSSIBLE\n");

    return 0;

}


Measured memory_bytes: 1404
#include <iostream>	
#include <string>
#include <algorithm>
#include <vector>
#include <list>
using namespace std;
typedef unsigned long long LL;
//
//int com(int n, int r) {
//	if (n == r || n == 0)return 0;
//}
//
//
//int main()
//{
//	string s;
//	int k;
//
//	
//
//	int a['z'] = { 0 };
//	for (int i = 0; i < s.length; i++)
//	{
//		a[s[i]] ++;
//	}
//	int count = 0;
//	for (int i = 'a'; i <'z' ; i++)
//	{
//		if (a[i] != 0)count++;
//	}
//	if (count < s.length > k) {
//		cout << "0"<<endl;
//		return 0;
//	}
//
//
//}
//
//LL visit(int x, int y) {
//	static int count = 0;
//	if (x == 0 && y == 0) {		
//		count++;
//		return count;
//	}
//if (x != 0)visit(x - 1, y);
//	if (y != 0)visit(x, y - 1);
//
//}
//
//int main() {
//	int N1,N2;
//	cin >> N1>>N2;
//	cout << visit(N1, N2) << endl;
////}
//
////}
//
//int mian() {
//	LL n;
//	cin >> n;
//	vector<int> a(n);
//	LL count;
//	cin >> count;
//
//	for (int i = 0; i < n; i++)
//		cin >> a[i];
//
//	int max=a[0], mix=a[0];
//	for (int i = 0; i < n; i++) {
//		if (max < a[i])max = a[i];
//		if (mix > a[i])mix = a[i];
//	}
//}
//
//int main() {
//	LL score = 0;
//	LL s,p;
//	for (int i = 0; i < 3; i++) {
//		cin >> s >> p;
//		score += s*p/10;
//	}
//	cout << score << endl;
//
//
//}
int main() {
	string s;
	cin >> s;
	for (int i = 0; i < s.length(); i += 2) {
		cout << s[i];
	}
	cout <<endl;
}


Measured memory_bytes: 512
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Scanner;

/**
 * Multiplication 3
 * https://atcoder.jp/contests/abc169/tasks/abc169_c
 */
public class Main {
	public static void main(String...args) {
		try (Scanner sc= new Scanner(System.in)) {
			BigDecimal a = BigDecimal.valueOf(sc.nextLong());
			BigDecimal b = BigDecimal.valueOf(sc.nextDouble());
			BigDecimal tmp = a.multiply(b);
			BigInteger ans = tmp.toBigInteger();
			System.out.println(ans);
		}
	}
}

Measured memory_bytes: 29188
#include <bits/stdc++.h>
#include <algorithm>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(x) (x).begin(), (x).end()
#define PB(x) push_back(x)
#define MP(x,y) make_pair(x,y)
using namespace std;
typedef long long ll;

int dp[1000000][11];
 
int main() {
    
    string s;
    cin>>s;

    ll n=s.size();
    vector<ll> d;
    for(int i=n-1;i>=0;i--) {
        ll num=s[i]-48;
        d.PB(num);
    }
    ll m=d.size();
    ll ans=0;
    rep(i,m) {
        if(i==m-1) {
            if(d[i]>5)  ans+=(10-d[i]+1);
            else    ans+=d[i];
        }
        else if(d[i]>=6||d[i]==5&&d[i+1]>=5) {
            ans+=(10-d[i]);
            d[i+1]++;       
        }
        else ans+=d[i];
    }

    cout<<ans<<endl;

 
 return 0;
}

Measured memory_bytes: 11768
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int K ;
  string S ;
  cin >> K >> S ;
  int res = 0 ;
  for(int i = 0; i < (K-2); i++){
   if (S.at(i)=='A'&&S.at(i+1)=='B'&&S.at(i+2)=='C'){
   res++;
   }
  }
  cout << res << endl;
 
  return 0 ;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(i=0;i<n;i++)
#define loop(i,a,n) for(i=a;i<n;i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

typedef vector<int> vi;
typedef pair<int,int> pii;

int main(void) {
  int i,j;
  int n;
  cin>>n;
  rep(i,n){
    int x,y,b,p;
    cin>>x>>y>>b>>p;
    int ans=0;
    if(b>=5 && p>=2)
      ans=(x*b+y*p)*0.8;
    else if(b>=5)
      ans=min((double)x*b+y*p,(x*b+y*2)*0.8);
    else if(p>=2)
      ans=min((double)x*b+y*p,(x*5+y*p)*0.8);
    else
      ans=min((double)x*b+y*p,(x*5+y*2)*0.8);
    cout<<ans<<endl;
  }
}

Measured memory_bytes: 3092
'use strict'
let input = require("fs").readFileSync("/dev/stdin", "utf8");
let Nums = input.split('');
let A = Nums[0];
let B = Nums[1];
let C = Nums[2];
let D = Nums[3];
let Sign = ["+","-"]
let ans = "";
// 多重ループ抜け用のラベル
forStop:
for(let i = 0; i < 2; i++){
  for(let j = 0; j < 2; j++){
	for(let k = 0; k < 2; k++){
      if((eval(A + Sign[i] + B + Sign[j] + C + Sign[k] + D)==7)){
        ans = A + Sign[i] + B + Sign[j] + C + Sign[k] + D　+ "=7";
        break forStop;
      }
	}
  }
}
console.log(ans);


Measured memory_bytes: 9420
#include <bits/stdc++.h>
using namespace std;
using vec = vector<int>;
using intk = int64_t;

int main() {
int N;
  cin >> N;
  vec A(N);
  for(int i=0;i<N;i++) cin >> A[i];
  vec B(N);
  for(int i=0;i<N;i++) B[i] = A[i];
  sort(A.begin(),A.end());
  for(int i=0;i<N;i++){
    if(B[i] == A[N-1]) cout << A[N-2] <<endl;
  else cout << A[N-1] <<endl;
  }
}
  


Measured memory_bytes: 3200
/*
confirm 0LL and 1LL
confirm cornercases such as 0
confirm times of cin < 10^6
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using Vec = vector<ll>;
using VecP = vector<P>;
using VecB = vector<bool>;
using VecC = vector<char>;
using VecS = vector<string>;
using VecVec = vector<Vec>;
using Tree = vector<VecP>;
#define REP(i, m, n) for(ll (i) = (m); (i) < (n); ++(i))
#define REPN(i, m, n) for(ll (i) = (m); (i) <= (n); ++(i))
#define REPR(i, m, n) for(ll (i) = (m)-1; (i) >= (n); --(i))
#define REPNR(i, m, n) for(ll (i) = (m); (i) >= (n); --(i))
#define rep(i, n) REP(i, 0, n)
#define repn(i, n) REPN(i, 1, n)
#define repr(i, n) REPR(i, n, 0)
#define repnr(i, n) REPNR(i, n, 1)
#define all(s) (s).begin(), (s).end()
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fs first
#define sc second
template <typename T>
bool chmax(T &a, const T& b){if(a < b){a = b; return true;} return false;}
template <typename T>
bool chmin(T &a, const T& b){if(a > b){a = b; return true;} return false;}
template <typename T>
void co(const T n){cout << n << endl;}
template <typename T>
void cosp(const T n){cout << n << ' ';}
void coVec(const Vec &v){for(ll i : v) cosp(i); cout << endl;}
void sonic(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);}
void setp(const ll n){cout << fixed << setprecision(n);}
const ll INF = 1e9+1;
const ll LINF = 1e18+1;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const double PI = acos(-1);
const double EPS = 1e-9;

Vec dp(100001, LINF);

int main(void){
	ll n, w;
	cin >> n >> w;
	VecP np(n);
	rep(i, n) cin >> np[i].fs >> np[i].sc;

	dp[0] = 0;
	rep(i, n) repr(j, 100001)
		if(j >= np[i].sc) chmin(dp[j], dp[j-np[i].sc]+np[i].fs);
	repr(i, 100001) if(dp[i] <= w){
		co(i);
		break;
	}

	return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>

int main(void)
{
	long int D,c[26],i,j;
	scanf("%ld",&D);
	for(i=0;i<26;i++){
		scanf("%ld",&c[i]);
	}
	long int s[D][26];
	for(i=0;i<D;i++){
		for(j=0;j<26;j++){
			scanf("%ld",&s[i][j]);
		}
	}
	
	for(i=0;i<D;i++){
      printf("%d\n",15);
    }
  
	return 0;
}


Measured memory_bytes: 1772
#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
#define for0(i, n) for(int i = 0; i < (n); i++)
#define for1(i, n) for(int i = 1; i <= (n);i++)
#define mp make_pair
#define all(x) x.begin(),x.end()
using namespace std;
struct S {
	int num = mod;
	vector<S*>list;
};
S top[1234];
S ss[510000]; int sssize = 0;
int n, q;
void ssinsert(S s1) {
	ss[sssize] = s1;
	sssize++;
}

bool dumpb = 0;
void dump(S* s1) {
	if ((*s1).num != mod) {
		if (dumpb) cout << ' ';
		cout << (*s1).num;
		dumpb = 1;
	}
	for (S* s2 : (*s1).list)dump(s2);
}

signed main() {
	cin >> n >> q;
	for1(valsqotch, q) {
		int a, b, c; cin >> a;
		if (a == 0) {
			S s1;
			cin >> b >> s1.num;
			ssinsert(s1);
			top[b].list.push_back(&(ss[sssize - 1]));
		}
		else if (a == 1) {
			cin >> b;
			dump(&(top[b]));
			cout << endl;
			dumpb = 0;
		}
		else {
			cin >> b >> c;
			S s1 = top[b];
			ssinsert(s1);
			top[c].list.push_back(&(ss[sssize - 1]));
			top[b].list.clear();
		}
	}
}


Measured memory_bytes: 45372
#include<iostream>

using namespace std;

int main()
{
  int n;
  cin>>n;
  int save=n;
  cout<<n<<":";
  for(int i=2;i*i<=save;i++)
    if(n%i==0)
      {
	while(n%i==0){
	  n/=i;
	  cout<<" "<<i;
	}
      }
  if(n>1)
    cout<<" "<<n;
  cout<<endl;
  
  return 0;
}

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

int main() {
  int N, sum = 0, t;
  cin >> N;
  t = N;
  while (t>0){
  sum += t %10;
  t = t / 10;
  }
  if (N % sum == 0) {
  cout  << "Yes"   <<  endl;
  }
  else{
  cout <<"No"<< endl;  
  }
}

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

using namespace std;

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

#define MOD 1000000007
#define REP(i, N) for (int i = 0; i < N; ++i)
#define REP1(i, N) for (int i = 1; i <= N; ++i)
#define RREP(i, N) for (int i = N - 1; i >= 0; --i)
#define ALL(a) a.begin(), a.end()

int main() {
  int n, k;
  cin >> n >> k;
  string s;
  cin >> s;
  s += "#";
  vector<int> sum;
  char before = s[0];
  int cnt = 0;
  for (int i = 0; i < n + 1; ++i) {
    if (s[i] != before) {
      if (before == '1') {
        sum.push_back(cnt);
      } else {
        sum.push_back(-cnt);
      }
      cnt = 1;
    } else {
      cnt++;
    }
    before = s[i];
  }
  cnt = 0;
  ll ans = 0, res = 0;
  int r = 0;
  for (int l = 0; l < sum.size(); ++l) {
    while (r < sum.size()) {
      if (0 < sum[r]) {
        res += sum[r];
        r++;
      } else {
        if (k <= cnt) break;
        cnt++;
        res -= sum[r];
        r++;
      }
    }
    ans = max(ans, res);
    if (l == r) {
      r++;
    } else {
      if (sum[l] < 0) {
        cnt--;
        res += sum[l];
      } else {
        res -= sum[l];
      }
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1020
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int64_t i = 0; i < (int64_t) (n); ++i)
#define pb emplace_back
#define endl '\n'

template<typename T> void _dbg(const char*_s,T _h) { cerr<<_s<<" = "<<_h<<"\n"; }

template<typename T, typename... Ts> void _dbg(const char*_s,T _h,Ts... _t) {
    for(int _b=0;((_b+=*_s=='(')-=*_s==')')!=0||*_s!=',';)cerr<<*_s++;
    cerr<<" = "<<_h<<",";_dbg(_s+1,_t...);
}

#define int long long

#ifdef LOCAL
    #define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
    #define dbg(...)
#endif

const int N = 300 * 1000 + 17;
const int MOD = 1000 * 1000 * 1000 + 7;

int n, a, b, c;
int F[N];

bool read() {
    if (!(cin >> n >> a >> b >> c))
        return false;

    return true;
}

int bp(int a, int n) {
    int res = 1;

    for (; n > 0; n /= 2, (a *= a) %= MOD)
        if (n & 1)
            (res *= a) %= MOD;

    return res;
}

int rev(int x) { return bp(x % MOD, MOD - 2); }

int binomial(int n, int k) { return F[n] * rev(F[k] * F[n - k] % MOD) % MOD; }

void solve() {
    F[0] = 1;

    forn (i, N - 1)
        F[i + 1] = (i + 1) * F[i] % MOD;

    int t = a + b;
    (a *= rev(t)) %= MOD;
    (b *= rev(t)) %= MOD;
    (c *= rev(100)) %= MOD;
    int ans = 0;

    for (int m = n; m < 2 * n; ++m) {
        int iv = rev(MOD + 1 - c) % MOD;
        int p1 = bp(a, n) * bp(b, m - n) % MOD;
        int p2 = bp(b, n) * bp(a, m - n) % MOD;
        int p = (p1 + p2) * binomial(m - 1, n - 1) % MOD;
        int e = iv * m % MOD * p % MOD;
        (ans += e) %= MOD;
    }

    cout << (MOD + ans % MOD) % MOD << endl;
}

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

    while (read())
        solve();

    return 0;
}



Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define LLINF 9223372036854775807
#define MOD ll(1e9+7)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cerr<<#x<<": "<<x<<endl


int main(){
    ll n;
    cin >> n;

    map<string,ll> mp;
    ll ans = 0;
    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        sort(all(s));
        ans += ++mp[s]-1;
    }

    cout << ans << endl;
    return 0;

}


Measured memory_bytes: 11136
#include <bits/stdc++.h>
#ifdef _DEBUG
#include "../../../debug_print.hpp"
#else
#define debug(...)
#endif
#define sort_(a) sort(a.begin(), a.end())
#define rsort(a) sort(a.rbegin(), a.rend())
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = n - 1; 0 <= i; i--)
#define for_(i, start, end) for (int i = start; i < end; i++)
#define rfor(i, start, end) for (int i = start - 1; 0 <= i; i--)
#define all(a) a.begin(), a.end()
using ll = long long;
using ld = long double;
using namespace std;
constexpr int INF32       = 1'050'000'000;
constexpr long long INF64 = 4'000'000'000'000'000'000;
constexpr int MOD7        = 1'000'000'007;
constexpr int MOD53       = 998'244'353;
constexpr double PI       = 3.14159265358979323846;
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;
}
void print() { std::cout << '\n'; }
template <class H, class... T> void print(H &&head, T &&... args) {
    std::cout << head;
    sizeof...(args) == 0 ? std::cout << "" : std::cout << ' ';
    print(std::forward<T>(args)...);
}
template <class T> void print(std::vector<T> &v) {
    for (int i = 0; i < v.size(); i++) {
        std::cout << v[i];
        i == v.size() - 1 ? std::cout << '\n' : std::cout << ' ';
    }
}
template <class T> void print(std::vector<std::vector<T>> &v) {
    for (int i = 0; i < v.size(); i++) {
        for (int j = 0; j < v[i].size(); j++) {
            std::cout << v[i][j];
            j == v[i].size() - 1 ? std::cout << '\n' : std::cout << ' ';
        }
    }
}
void scan() {}
template <class H, class... T> void scan(H &&head, T &&... args) {
    std::cin >> head;
    scan(std::forward<T>(args)...);
}
template <class T> void scan(std::vector<T> &v) {
    for (auto &&i : v) {
        scan(i);
    }
}

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

    string s;
    scan(s);
    int ans = 0;
    for (auto &&i : s) {
        if (i == '1')
            ans++;
    }
    print(ans);

    return 0;
}

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



int main(){
	int i,j,k,n,m,l,f,x,y,z; string s;
	string w[105];
	cin >> n;
	rep(i, n) cin >> w[i];

	set<string> se;

	rep(i, n){
		se.insert(w[i]);
	}

	f = 0;
	REP(i, 1, n){
		if(w[i-1][w[i-1].size()-1] != w[i][0]){
			f = 1;
			break;
		}
	}

	if(f == 0 && se.size() == n) cout << "Yes";
	else cout << "No";

}

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

	cin >>n>>m;
	int p[100001][2];
	int p1;
	string s1;
	int acc=0;
	int wac=0;
	rep(i,100001)rep(j,2)p[i][j]=0;
	rep(i,m){
		cin >> p1>>s1;
		if (s1=="WA"){
			if(p[p1][0]!=1){
				p[p1][1]++;
			}
		}
		if (s1=="AC"){
			p[p1][0]=1;
		}
	}
	rep(i,n+1){
		if(p[i][0]==1){
			acc++;
			wac+=p[i][1];
		}
	}
	cout << acc << " " <<wac<<endl;
	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include "stdio.h"

using namespace std;

#define mod 1000000007
#define int long long
#define fio ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL)
#define psb push_back

const int maxn=2e5+5;
int ar[maxn];


void solve()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>ar[i];
    int mx=ar[0],ans=0;
    for(int i=1;i<n;i++){
        ans += max(0ll, mx-ar[i]);
        mx=max(mx,ar[i]);
    }
    cout<<ans<<endl;
}

int32_t main()
{
    fio;
    int t;
    // cin>>t;
    t=1;
    while(t--)
        solve();
}

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

bool isContain3(int n) {
	int x = n;
	do {
		if(x % 10 == 3) {
			return true;
		}
		x /= 10;
	} while(x != 0);

	return false;
}

bool isMultipliesOf3(int n) {
	return (n % 3 == 0);
}

int main() {
	int n;
	cin >> n;
	for(int x = 3; x <= n; ++x) {
		if(isContain3(x) || isMultipliesOf3(x)) {
			cout<< " " << x ;
		}
	}
	cout << endl;
	
	return 0;
}

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

//最小公倍数= a*b / 最大公約数
//最大公約数
long long gcd(long long x, long long y){
    return y ? gcd(y, x%y) : x;
}

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

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

    vector<int> xs(N);
    for (int i = 0; i < N; ++i){
        xs[i] = abs(x[i] - X);
    }

    int ans = xs[0];
    for (int i = 1; i < N; ++i){
        ans = gcd(ans,xs[i]);
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cmath>
#include <sstream>
#include <algorithm>
using namespace std;

typedef long long ll;
typedef pair<int,int> P;
const int MAX=1000000000;

int main() {
  int n;
  while(cin >> n && n) {
    string s[n];
    int dp[n][n];
    for(int i=0; i<n; i++) {
      cin >> s[i];
      for(int j=0; j<n; j++) {
	if(s[i][j]=='.') dp[i][j]=1;
	else dp[i][j]=0;
      }
    }
    int ans=0;
    for(int i=1; i<n; i++) {
      for(int j=1; j<n; j++) {
	if(s[i][j]=='.') {
	  if(dp[i-1][j-1]>0 && dp[i-1][j]>0 && dp[i][j-1]>0) dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;
	}
	ans=max(ans,dp[i][j]);
      }
    }
    cout << ans << endl;
  }
  return 0;
}


Measured memory_bytes: 6160
from bisect import bisect


def check_neg(m, k, pos, neg, len_pos):
    less = 0  # かけたら m 未満になるペア数
    j = 0
    for a in neg:
        d = m // a
        while j < len_pos and pos[j] <= d:
            j += 1
        if len_pos == j:
            break
        less += len_pos - j
    return less < k


def check_pos(m, k, pos, neg, len_pos, len_neg):
    less_eq = 0  # かけたら m 以下になるペア数
    j = 0
    for i in range(len_pos - 1, -1, -1):
        a = pos[i]
        d = m // a
        while j < len_pos and pos[j] <= d:
            j += 1
        if j == len_pos:
            less_eq += len_pos * (i + 1)
            break
        less_eq += j

    j = 0
    for i in range(len_neg - 1, -1, -1):
        a = neg[i]
        d = m // a
        while j < len_neg and neg[j] <= d:
            j += 1
        if j == len_neg:
            less_eq += len_neg * (i + 1)
            break
        less_eq += j

    m_sqrt = int(m ** 0.5)
    less_eq -= bisect(pos, m_sqrt)
    less_eq -= bisect(neg, m_sqrt)

    less_eq //= 2

    return less_eq < k


def solve(n, k, aaa):
    pos = [a for a in aaa if a > 0]
    neg = [a for a in aaa if a < 0]
    len_pos = len(pos)
    len_neg = len(neg)
    neg_mul = len_pos * len_neg
    pos_mul = len_pos * (len_pos - 1) // 2 + len_neg * (len_neg - 1) // 2
    if neg_mul >= k:
        l = -(10 ** 18)
        r = 0
        while l + 1 < r:
            m = (l + r) // 2
            if check_neg(m, k, pos, neg, len_pos):
                l = m
            else:
                r = m
        return l
    elif n * (n - 1) // 2 - pos_mul >= k:
        return 0
    else:
        k -= n * (n - 1) // 2 - pos_mul
        l = 0
        r = 10 ** 18
        neg = [-a for a in neg]
        neg.reverse()
        while l + 1 < r:
            m = (l + r) // 2
            if check_pos(m, k, pos, neg, len_pos, len_neg):
                l = m
            else:
                r = m
        return r


n, k = map(int, input().split())
aaa = list(map(int, input().split()))
aaa.sort()
print(solve(n, k, aaa))


def debug():
    mul = []
    for i in range(n):
        for j in range(i + 1, n):
            mul.append(aaa[i] * aaa[j])
    mul.sort()
    print(mul[k - 1], mul)

# debug()


Measured memory_bytes: 96596
package main

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

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getInts(N int) []int {
	ret := make([]int, N)
	for i := 0; i < N; i++ {
		ret[i] = getInt()
	}
	return ret
}

func getString() string {
	sc.Scan()
	return sc.Text()
}

// min, max, asub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func asub(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}

func lowerBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] >= x
	})
	return idx
}

func upperBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] > x
	})
	return idx
}

const inf = math.MaxUint64 >> 1

func main() {
	sc.Split(bufio.ScanWords)
	sc.Buffer([]byte{}, 1000000)
	N, K := getInt(), getInt()
	p := make([]int, N)
	for i := 0; i < N; i++ {
		p[i] = getInt() - 1
	}
	c := getInts(N)
	ans := -inf
	for i := 0; i < N; i++ {
		used := make([]bool, N)
		score := make([]int, 0)
		ps := 0
		next := p[i]
		for used[next] != true {
			// out(next)
			used[next] = true
			score = append(score, ps+c[next])
			ps = ps + c[next]
			next = p[next]
		}
		n := K / len(score)
		m := K % len(score)
		if n > 0 {
			n--
			m += len(score)
		}
		var sum int
		if score[len(score)-1] >= 0 {
			sum = max(0, score[len(score)-1]*n)
			ma := 0
			next := p[i]
			tot := 0
			for j := 0; j < m; j++ {
				tot += c[next]
				ma = max(ma, tot)
				next = p[next]
				// ma = max(ma, score[j%len(score)])
			}
			sum += ma
		} else {
			ma := -inf
			l := min(len(score), K)
			for j := 0; j < l; j++ {
				ma = max(ma, score[j])
			}
			// out(score, ma)
			sum = ma
		}
		ans = max(ans, sum)
	}
	out(ans)
}


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

#define dump(...) cout<<"# "<<#__VA_ARGS__<<'='<<(__VA_ARGS__)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple

using uint=unsigned;
using ll=long long;
using ull=unsigned long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using vd=vector<double>;
using vvd=vector<vd>;
using vs=vector<string>;

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}

template<typename Tuple>
void print_tuple(ostream&,const Tuple&){}
template<typename Car,typename... Cdr,typename Tuple>
void print_tuple(ostream& os,const Tuple& t){
	print_tuple<Cdr...>(os,t);
	os<<(sizeof...(Cdr)?",":"")<<get<sizeof...(Cdr)>(t);
}
template<typename... Args>
ostream& operator<<(ostream& os,const tuple<Args...>& t){
	print_tuple<Args...>(os<<'(',t);
	return os<<')';
}

template<typename Ch,typename Tr,typename C>
basic_ostream<Ch,Tr>& operator<<(basic_ostream<Ch,Tr>& os,const C& c){
	os<<'[';
	for(auto i=begin(c);i!=end(c);++i)
		os<<(i==begin(c)?"":" ")<<*i;
	return os<<']';
}

constexpr int INF=1e9;
constexpr int MOD=1e9+7;
constexpr double EPS=1e-9;

int main()
{
	for(int n;cin>>n&&n;){
		vl a(n);
		rep(i,n) cin>>a[i];

		sort(all(a),greater<ll>());

		ll res=0;
		for(;;){
			int i=max_element(all(a))-begin(a);
			if(a[i]<n) break;
			ll cnt=a[i]/n;
			rep(j,n){
				if(j==i)
					a[j]-=cnt*n;
				else
					a[j]+=cnt;
			}
			res+=cnt;
		}
		cout<<res<<endl;
	}
}


Measured memory_bytes: 256
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

def LI(): return list(map(int,input().split()))
def I(): return int(input())
def LS(): return input().split()
def S(): return input()

def main():
  n=I()
  l=LI()

  dp=[0]*100010

  dp[0]=0
  dp[1]=abs(l[1]-l[0])

  for i in range(2,n):
    dp[i]=min(dp[i-2]+abs(l[i-2]-l[i]),dp[i-1]+abs(l[i-1]-l[i]))

  return dp[n-1]

print(main())


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

typedef long long ll;
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define REP(i,n) for (int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
 
using namespace std;

int main(){
    ll n;
    cin >> n;

     if(n%2) cout << 2*n << endl; 
     else cout << n << endl;
    return 0;
}


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

typedef long long ll;

#define pb push_back
#define mkp make_pair
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define clr(a, b) memset(a, b, sizeof(a))
#define forn(i, n) for(int i=0; i<(int)(n); ++i)
#define forab(i, a, b) for(int i=(int)(a); i<=(int)(b); ++i)
#define FOR(it,c) for ( __typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++ )

vector<string> num;
deque<int> d[10];

void rec(int pos, string p) {
    if(pos > 3)
        return;
    if(pos == 3) {
        num.pb(p);
        return;
    }
    forab(i, 0, 9) {
        rec(pos+1, string(p + char(i + '0'))); 
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
#ifdef LOCAL
    clock_t tStart = clock();
#endif
    rec(0, "");
    int n;
    string s;
    cin >> n >> s;
    forn(i, n) {
        d[s[i] - '0'].pb(i);
    }
    int res = 0;
    for(string ss: num) {
        int last = -1;
        forn(i, ss.length()) {
            int lo = upper_bound(all(d[ss[i] - '0']), last) - d[ss[i] - '0'].begin();
            if(lo != (int)d[ss[i] - '0'].size()) {
                last = d[ss[i]-'0'][lo];
            } else {
                last = -1;
                break;
            }
        }
        if(last != -1) {
            ++res;
        }
    }
    cout << res << "\n";
#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * (clock() - tStart)/ CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}


Measured memory_bytes: 512
/**
* 氏名: 阿部寛之
* 学籍番号: 170441004
***/


#include<stdio.h>

int main(void)
{
	int length, width;//縦、横

	scanf("%d %d", &length, &width);

	printf("%d %d\n", length * width, length * 2 + width * 2);
	return 0;
}


Measured memory_bytes: 2140
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder.Abc
{
    class QuestionD
    {
        public static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            // 整数の入力
            var n = int.Parse(Console.ReadLine());

            // 整数配列の入力
            var a = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();

            var aDic = new long[n];

            for(int i = 0; i < n; i++) {
                aDic[a[i] - 1]++;
            }

            var last = aDic.Where(x => x > 1).ToArray();

            var length = last.Count();
            var count = 0L;

            for (int i = 0; i < length; i++) {
                count += (last[i] * (last[i] - 1)) / 2L;
            }

            for (int i = 0; i < n; i++) {
                if (aDic[a[i] - 1] < 2) {
                    Console.WriteLine(count);
                    Console.Out.Flush();
                } else {
                    var nn = aDic[a[i] - 1];
                    Console.WriteLine(count - (nn - 1));
                    Console.Out.Flush();
                }
            }
        }
    }
}


Measured memory_bytes: 35648
#include <iostream>
using namespace std;
using ll = long long;
const int AMAX = 100000;
ll cnt[AMAX + 1];
int main(void) {
    int N;
    ll K;
    cin >> N >> K;
    for (int i = 0; i < N; ++i) {
        int A, B;
cin >> A >> B;
cnt[A] += B; }
    for (int ans = 1; ans <= AMAX; ++ans){
        if (K <= cnt[ans]) {
            cout << ans << endl;
break; }
        K -= cnt[ans];
    }
return 0; }

Measured memory_bytes: 1152
n,m=map(int,input().split())
path=[[0]*n for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    path[a-1][b-1]=1
    path[b-1][a-1]=1

def connected(v,visited):
    visited[v]=1
    if sum(visited)==n:
        visited=[0]*n
        return 1
    count=0
    for i in range(n):
        if path[v][i]==1 and visited[i]==0:#行ったことある点にはいかない
            visited[i]=1#行ったことを記録
            count+=connected(i,visited)
    visited=[0]*n
    return count
bridge=0

for x in range(n):
    for y in range(x+1,n):
        if path[x][y]==1:
            visited=[0]*n
            path[x][y]=0
            if not connected(x,visited):
                bridge+=1
            path[x][y]=1
print(bridge)

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <functional>
#include <ctime>
#include <cmath>
#include <limits>
#include <numeric>
#include <type_traits>
#include <iomanip>
#include <float.h>
#include <math.h>
using namespace std;
using ll = long long;


unsigned euclidean_gcd(unsigned a, unsigned b) {
    if (a < b) return euclidean_gcd(b, a);
    unsigned r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}

class UnionFind {
public:
    vector <ll> par;
    vector <ll> siz;
    UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL) {
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1LL);
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    ll root(ll x) {
        while (par[x] != x) {
            x = par[x] = par[par[x]];
        }
        return x;
    }
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool issame(ll x, ll y) {
        return root(x) == root(y);
    }

    ll size(ll x) {
        return siz[root(x)];
    }
};

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

long long modinv(long long a, long long mod) {
    return modpow(a, mod - 2, mod);
}

int main() {
    ll n;
    cin >> n;
    vector<ll> z(n);
    ll mxabs = 0;
    ll now = 0;
    for (int i = 0; i < n; i++) {
        cin >> z[i];
        mxabs = max(mxabs, abs(z[i]));
        if (mxabs == abs(z[i]))now = i;
    }
    cout << 2 * n << endl;
    if (z[now] < 0) {
        cout << now + 1 << " " << n << endl;
        cout << now + 1 << " " << n << endl;
        for (int i = n; i > 1; i--) {
            cout << i << " " << i-1 << endl;
            cout << i << " " << i-1 << endl;
        }
    }
    else {
        cout << now + 1 << " " << 1 << endl;
        cout << now + 1 << " " << 1 << endl;
        for (int i = 1; i < n;i++) {
            cout << i << " " << i + 1 << endl;
            cout << i << " " << i + 1 << endl;
        }
    }
}

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

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n; cin>>n;
  vector<pair<int,int>> A(n,pair<int,int>(0,0));
  rep(i,n){
    int a; cin>>a;
    A.at(i).first=a;
    A.at(i).second=i+1;
  }
  sort(A.begin(),A.end());
  rep(i,n) cout<<A.at(i).second<<' ';
}

Measured memory_bytes: 1664
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<ll>;
using vvi = vector<vi>;
const int INF = 100010001;
const ll LINF = (ll)INF*INF*10;

int main() {
    int n;
    cin >> n;
    vi a(n);
    rep(i, n) {
        cin >> a[i];
    }

    sort(all(a));
    ll sum = a[0];
    ll ans = 1;
    rep(i, n-1) {
        if(a[i+1] > 2*sum) ans = 1;
        else ans++;
        sum += a[i+1];
    }

    cout << ans << endl;
}

Measured memory_bytes: 1024
from bisect import *

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

s = input()
K = read()
L = len(s)
sbs = sorted(set(s[i:i+j] for i in range(L) for j in range(1, K+1) if i + j <= L))
print(sbs[K-1])

Measured memory_bytes: 40400
import numpy as np
n, m, c = map(int, input().split())
b = np.array(tuple(map(int, input().split())))
ans = 0
for i in range(n):
    a = np.array(tuple(map(int, input().split())))
    if np.dot(a, b) + c > 0:
        ans += 1

print(ans)

Measured memory_bytes: 12504
import sys
input=sys.stdin.readline
n,m,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
A=[0]
B=[0]
for i in range(n):
    A.append(A[i]+a[i])
for i in range(m):
    B.append(B[i]+b[i])
import bisect
ans=0
for i in range(n+1):
    if A[i]<=k:
        j=bisect.bisect(B,k-A[i])
        temp=i+j-1
        ans=max(ans,temp)
print(ans)


Measured memory_bytes: 124896
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in)) {
            int N = sc.nextInt();

            int[] a = new int[N + 1];
            for (int i = 1; i <= N; i++) {
                if (i % 3 == 0 || i % 5 == 0) {
                    continue;
                }
                a[i] = i;
            }

            long sum = 0;
            for (int i = 1; i <= N; i++) {
                sum += a[i];
            }

            System.out.println(sum);
        }
    }
}


Measured memory_bytes: 31052
import collections
import math
N, A, B = map(int, input().split())
value = list(map(int, input().split()))
value.sort()
value.reverse()
valuetot = 0
for i in range(A):
    valuetot += value[i]
valueave = valuetot/A
value.append(0)
v = value[A-1]
C = collections.Counter(value)
vcount = C[v]

for i in range(A):
    if value[i] == v:
        vindex = i
        break

def permutation(n,r):
    r = min(r, n-r)
    numerator = 1
    for i in range(n, n-r, -1):
        numerator *= i
    denominator = 1
    for i in range(r, 1, -1):
        denominator *= i
    return numerator // denominator


def pattern(a):
    c = collections.Counter(value[:a])
    return permutation(vcount, c[v])

v0 = value[0]
v0len = 0
for i in range(N):
    if v0 == value[i]:
        v0len = i + 1
    else:
        break


if v0len >= A:
    ans = 0
    for i in range(A-1, B):
        if v0 == value[i]:
            ans += permutation(v0len, i+1)


elif value[A-1] != value[A]:
    ans = 1

else:
    ans = pattern(A)

print(valueave)
print(ans)


Measured memory_bytes: 3316
#ifdef LOCAL
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstring>
#else
#include <bits/stdc++.h>
#endif
using namespace std ;

typedef long long ll ;
#define rep(i , n ) for ( int i =0; i < n ; i++)
#define _sort(arg) sort(begin(arg), end(arg))
#define MOD 1000000007
#define pb push_back
#define DEBUG(x) cout << #x << ": " << x << endl;

/*
__attribute__((constructor))
void initial()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);
}
*/

bool is_not_month(int a)
{
	if ((a <= 0) || (a>12))
	{
		return true;
	}
	return false;
}

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

	string a;
	
	cin >> a;
	int d = stoi(a);
	int b = d / 100;
	int c = d % 100;
	if (is_not_month(b) && is_not_month(c))
	{
		cout << "NA" << endl;
	}
	else if (is_not_month(b) && !is_not_month(c))
	{
		cout << "YYMM" << endl;
	}
	else if (is_not_month(c) && (!is_not_month(b)))
	{
		cout << "MMYY" << endl;
	}
	else
	{
		cout << "AMBIGUOUS" << endl;
	}
	
	

	
	return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int MOD = 1e9+7;

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

    int k;
    string s;
    cin >> k >> s;

    int n = s.size();
    if(n <= k){
        cout << s << endl;
        return 0;
    }else{
        rep(i,k){
            cout << s[i];
        }
        cout << "..." << endl;
    }



    return 0;
}

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

void swap(int a, int b) {
	if (a > b) cout << b << " " << a << endl;
	else cout << a << " " << b << endl;
}
int main()
{
	int x[6000];
	int i = 0;
	while (true) {
		cin >> x[2 * i] >> x[2 * i + 1];
		if ((x[2 * i] == 0) && (x[2 * i + 1] == 0)) break;
		++i;
	}
	for (int n = 0; n < i; n++) {
		swap(x[2 * n], x[2 * n + 1]);
	}
}



Measured memory_bytes: 3096
use std::io;
use std::str;

fn solve<R: io::BufRead, W: io::Write>(scan: &mut Scanner<R>, out: &mut W) {
    let n: usize = scan.token();
    let mut p = Vec::new();
    for _ in 0..n {
        p.push(scan.token::<f64>());
    }

    // dp[n][nh]: the probability of obtaining nh heads from n coin tosses
    let mut dp = vec![vec![0.0; n + 1]; n + 1];
    dp[0][0] = 1.0;
    for i in 0..n {
        for ih in 0..=i {
            dp[i + 1][ih + 1] += dp[i][ih] * p[i];
            dp[i + 1][ih] += dp[i][ih] * (1.0 - p[i]);
        }
    }
    let mut ans = 0.0;
    for ih in (n / 2 + 1)..=n {
        ans += dp[n][ih];
    }
    writeln!(out, "{}", ans).ok();
}

fn main() {
    let (stdin, stdout) = (io::stdin(), io::stdout());
    let mut scan = Scanner::new(stdin.lock());
    let mut out = io::BufWriter::new(stdout.lock());
    solve(&mut scan, &mut out);
}

pub struct Scanner<R> {
    reader: R,
    buffer: Vec<String>,
}

impl<R: io::BufRead> Scanner<R> {
    pub fn new(reader: R) -> Self {
        Self {
            reader,
            buffer: vec![],
        }
    }

    pub fn token<T: str::FromStr>(&mut self) -> T {
        loop {
            if let Some(token) = self.buffer.pop() {
                return token.parse().ok().expect("Failed parse");
            }
            let mut input = String::new();
            self.reader.read_line(&mut input).expect("Failed read");
            self.buffer = input.split_whitespace().rev().map(String::from).collect();
        }
    }

    pub fn tokens<T: str::FromStr>(&mut self) -> Vec<T> {
        assert!(self.buffer.is_empty());
        let mut input = String::new();
        self.reader.read_line(&mut input).expect("Failed read");
        input
            .split_whitespace()
            .map(|x| x.parse().ok().expect("Failed parse"))
            .collect()
    }
}


Measured memory_bytes: 72488
#include<bits/stdc++.h>
using namespace std;
main(){
  int K,S,ans=0;
  cin>>K>>S;
  for(int X=0;X<=K;++X){
    int YZ=S-X;
    if(YZ<0)continue;
    for(int Y=0;Y<=K;++Y){
      int Z=YZ-Y;
      if(Z<0||K<Z)continue;
      if(X+Y+Z==S){
        // printf("%d+%d+%d=%d\n",X,Y,Z,S);
        ++ans;
      }
    }
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define INF 1e9
#define PI 3.14159265359
#define MOD 1000000007
#define ALL(v) v.begin(),v.end()
#define ALLR(v) b.rbegin(),v.rend()
typedef long long ll;
//isPrime
//modpow modinv
int main() {
  cout << fixed << setprecision(10);
  int n,k;
  cin >> n >> k;
  vector<double> a(n+1,0);
  rep(i,n){
    double p;
    cin >> p; 
    a[i+1]=a[i]+(p+1)/2;
  }
  double ans=0;
  for(int i=0; i+k<=n; i++){
    ans=max(ans,a[i+k]-a[i]);
  }
  cout << ans << endl;

}




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

int main() {
  int N;
  long double Ans=1, B=1000000000000000000;
  long long Ans1=-1;
  cin >> N;
  vector<long long> A(N);
  rep(i, N) cin >> A.at(i);
  sort(A.begin(), A.end());
  rep(i, N){
    Ans*=A.at(i);
    Ans1=(long long)(Ans);
    if(Ans>B){
      Ans1=-1;
      break;
    }
  }
  cout << Ans1 << endl;
}

Measured memory_bytes: 4020
//vvk
#include "bits/stdc++.h"
using namespace std;
 
using ll = long long;
 
const ll inf = 1e18;
const int N = 2 * 1e5 + 1;

ll res , k , n;
ll w[105] , v[105] , dp[105][N];

ll go(ll idx , ll sum) {
    if(idx >= n) {
        if(sum <= k) return 0;
        else return -inf;
    }
    if(dp[idx][sum] != -1) return dp[idx][sum];
    ll xx = 0 , yy = 0;
    if(w[idx] + sum <= k) {
        xx = v[idx] + go(idx + 1 , sum + w[idx]);
    }
    yy = go(idx + 1 , sum);

    return dp[idx][sum] = max(xx , yy);
}

void solve(){
    cin >> n >> k;
    for(int i = 0; i < n; i++) {
        cin >> w[i] >> v[i];
    }
    memset(dp , -1 , sizeof(dp));
    cout << go(0 , 0);
}
 
int main(int argc, char const *argv[]){
    ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
    ll t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}

Measured memory_bytes: 167672
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <queue>

using namespace std;

class Node{
public:
	int p, q, c;
	Node(int p, int q, int c) : p(p), q(q), c(c) {}
	bool operator < (const Node &nd) const { return c > nd.c; }
};

const int INF = 1000000007;
typedef vector< vector<Node> > graph;

vector<int> getCost(const graph &g, int src, int cap){
	vector<bool> visit(g.size(), false);
	vector<int> res(g.size(), 10*cap+1);
	priority_queue< Node > qu; qu.push(Node(src, src, 0));
	res[src] = 0;
	while(!qu.empty()){
		Node nd = qu.top(); qu.pop();
		int pos = nd.q, cost = nd.c;
		if(visit[pos]) continue;
		for(int i=0;i<g[pos].size();i++){
			int next = g[pos][i].q;
			if(cost + g[pos][i].c < res[next]){
				res[next] = cost + g[pos][i].c;
				qu.push(Node(pos, next, res[next]));
			}
		}
	}
	return res;
}

int dijkstra(const graph &g, int src, int dst){
	vector<bool> visit(g.size(), false);
	vector<int> res(g.size(), INF);
	priority_queue< Node > qu; qu.push(Node(src, src, 0));
	res[src] = 0;
	while(!qu.empty()){
		Node nd = qu.top(); qu.pop();
		int pos = nd.q, cost = nd.c;
		if(visit[pos]) continue;
		for(int i=0;i<g[pos].size();i++){
			int next = g[pos][i].q;
			if(cost + g[pos][i].c < res[next]){
				res[next] = cost + g[pos][i].c;
				qu.push(Node(pos, next, res[next]));
			}
		}
	}
	return res[dst] < INF ? res[dst] : -1;
}

int main(){
	int N, M, cap;
	while(cin >> N >> M >> cap, N){
		string src, dst; cin >> src >> dst;
		map<string, int> mp;
		graph g1(2*N, vector<Node>());
		int idx = 0;
		for(int i=0;i<N;i++){
			string c1, c2; int d;
			cin >> c1 >> c2 >> d;
			if(!mp.count(c1)) mp[c1] = idx++;
			if(!mp.count(c2)) mp[c2] = idx++;
			g1[mp[c1]].push_back(Node(mp[c1], mp[c2], d));
			g1[mp[c2]].push_back(Node(mp[c2], mp[c1], d));
		}
		vector<int> LPG(M+2);
		for(int i=1;i<=M;i++){
			string s; cin >> s;
			LPG[i] = mp[s];
		}
		
		if(!mp.count(src)){ cout << -1 << endl; continue; }
		if(!mp.count(dst)){ cout << -1 << endl; continue; }

		LPG[0  ] = mp[src];
		LPG[M+1] = mp[dst];

		graph g2(M+2, vector<Node>());
		for(int i=0;i<M+2;i++){
			vector<int> vi = getCost(g1, LPG[i], cap);
			for(int j=0;j<M+2;j++){
				if(vi[LPG[j]] <= 10*cap)
					g2[i].push_back(Node(i, j, vi[LPG[j]]));
			}
		}

		cout << dijkstra(g2, 0, M+1) << endl;
	}
}

Measured memory_bytes: 3156
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author HARSHAD
 */

#include <bits/stdc++.h>
#define f(i,n) for(int i=0;i<n;i++)
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
typedef vector<int> vi;
typedef long long int ll;
vector<vector<int>> adj;

class D {
public:
	void solve(std::istream& in, std::ostream& out) {
		ll n, h; in>>n>>h;
		vector<ll> a(n), b(n);
		//ll max_index=-1, max_a=0;
		f(i, n){
			in>>a[i]>>b[i];
		}
		sort(a.rbegin(), a.rend());
		sort(b.rbegin(), b.rend());
		ll res = 0;
		int i=0;
		while(i<n and b[i]>=a[0] and h>0) res++, h-=b[i++];
		if(h>0) res+=ceil((double)h/a[0]);
		out<<res;
	}
    void inG(int m, istream& in){ int u,v; adj = vector<vi>(200005);f(i, m){ in>>u>>v; adj[u].push_back(v); adj[v].push_back(u); }}
};


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	D solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 1792
#include <iostream>

using namespace std;

int main() {
	int n, m;
	while (cin >> n >> m) {
		if (n == 0 && m == 0) {
			break;
		}
		int taro[100];
		int hanako[100];
		int taros = 0;
		int hanakos = 0;
		int sa;
		for (int i = 0; i < n; i++) {
			cin >> taro[i];
			taros += taro[i];
		}
		for (int i = 0; i < m; i++) {
			cin >> hanako[i];
			hanakos += hanako[i];
		}
		sa = taros-hanakos;
		int taroo , hanakoo;
		taroo = hanakoo = -1;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				int tem = taro[i]*2-hanako[j]*2;
				if (sa == tem) {
					if (taroo == -1 && hanakoo == -1) {
						taroo = taro[i];
						hanakoo = hanako[j];
					} else if (taroo+hanakoo > taro[i]+hanako[j]){
						taroo = taro[i];
						hanakoo = hanako[j];
					}
				}
			}
		}
		if (taroo != -1 && hanakoo != -1) {
		cout << taroo << " " << hanakoo << endl;
		} else {
			cout << -1 << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1156
using System;
using System.Linq;

namespace D
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int[] A = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            long sum = 1000;
            long Kabu = 0;
            for (int i = 0; i < n-1; i++)
            {
                if (A[i] < A[i + 1])
                {
                    //買う
                    Kabu = sum / A[i];
                    sum  %= A[i];
                    //売る
                    sum += (A[i + 1] * Kabu);
                    Kabu = 0;
                }
            }
            Console.WriteLine(sum);
        }
    }
}


Measured memory_bytes: 28312