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

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int[] array = new int[a];
		int w1 = 0;
		int w2 = 0;
		int min = 0;
		int flag = 0;
		for(int i = 0; i < array.length; i++) {
			array[i] = sc.nextInt();
		}
		for(int i = 1; i < array.length; i++) {
			for(int j = 0; j <= i; j++) {
				w1 += array[j];
			}
			for(int j = array.length - 1; j > i; j--) {
				w2 += array[j];
			}
			if(flag == 0) {
				min = Math.abs(w1 - w2);
				flag = 1;
			}else if(Math.abs(w1 - w2) < min) {
				min = Math.abs(w1 - w2);
			}
			w1 = 0;
			w2 = 0;
		}
		System.out.println(min);
	}
}

Measured memory_bytes: 23508
#include <iostream>
int main() {
	int x, a, b;
	std::cin >> x >> a >> b;
	if (b - a <= x) {
		if (b - a <= 0) {
			std::cout << "delicious" << std::endl;
		}
		else {
			std::cout << "safe" << std::endl;
		}
	}
	else {
		std::cout << "dangerous" << std::endl;
	}
}

Measured memory_bytes: 384
from itertools import product
N=int(input())
s=input()
s = s+s

ans = None
for s0, s1 in product(range(2), repeat=2):#0:wolf, 1:sheep
    tmp = [s0, s1]
    for i in range(1, N):
        if (tmp[i] == 0 and s[i] == "o") or (tmp[i] == 1 and s[i] == "x"):
            if tmp[i-1] == 0:
                tmp.append(1)
            else:
                tmp.append(0)
        else:
            if tmp[i-1] == 0:
                tmp.append(0)
            else:
                tmp.append(1)
    if s0 == tmp[-1]:
        if (s0 == 0 and s[0] == "o") or (s0 == 1 and s[0] == "x"):
            if s1 == tmp[-2]:
                continue
        else:
            if s1 != tmp[-2]:
                continue
        ans = tmp 
        break

if ans is None:
    print(-1)
else:
    ans = ans[:-1]
    final = ""
    for a in ans:
        if a == 0:
            final += "W"
        else:
            final += "S"
    print(final)

Measured memory_bytes: 111096
////////////////////////// Author
////////////////////////// Nasim Hossain Rabbi
////////////////////////// JU-CSE28
////////////////////////// CF - imnasim3.1415
////////////////////////// UVA - imnasim3.1415
////////////////////////// Mail - imnasim3.1415@gmail.com
#include<bits/stdc++.h>
using namespace std;
#define E end()
#define B begin()
#define sz size()
#define EM empty()
#define fi first
#define se second
#define cl clear()
#define sqr(a) (a*a)
#define mk make_pair
#define pb push_back
string en="\n";
string sp=" ";
string t="hello";
string Y="YES\n";
string N="NO\n";
#define rep(i,n) for(i=0;i<n;i++)
#define Rep(i,n) for(i=1;i<=n;i++)
#define per(i,n) for(i=n-1;i>=0;i--)
#define peR(i,n) for(i=n;i>0;i--)
#define mem(a,b) memset(a,b,sizeof(a))
#define all(cont) cont.begin(),cont.end()
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL)
#define pi 3.1415926535897932384626433832795
#define vi vector<long long>
#define vs  vector<string>
#define MX LLONG_MAX
#define MN LLONG_MIN
#define MOD 1000000007
#define vp(vi,x) cin>>x; vi.pb(x);
#define bsearch(a,x) binary_search(all(a),x)
#define LB(a,x) (lower_bound(all(a),x)-a.B)
#define UB(a,x) (upper_bound(all(a),x)-a.B)
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
bool isprm(LL a){for(LL i=2;i*i<=a;i++){if(a%i==0)return false;}return true;}
bool palin(string a){for(int i=0;i<a.sz;i++){if(a.at(i)!=a.at(a.sz-i-1))return 0;} return 1;}
bool isVowel(char ch){ ch=toupper(ch); if(ch=='A'||ch=='U'||ch=='I'||ch=='O'||ch=='E') return true; return false;}
int toInt(string s){int sm;stringstream ss(s);ss>>sm;return sm;}
LL bpow(LL a,LL b){if(b==0)return 1;LL r=bpow(a,b/2);if(b%2)return r*r*a;else return r*r;}
LL binpow(LL a,LL b){LL r=1;while(b>0){if(b&1)r=r*a;a=a*a;b>>=1;}return r;}
LL binpow(LL a,LL b,LL m){a%=m;LL r=1;while(b>0){if(b&1) r=r*a%m;a=a*a%m; b>>=1;}return r;}
template<typename T>inline T gcd(T a,T b){if(a<0)return gcd(-a,b);if(b<0)return gcd(a,-b);return (b==0)?a:gcd(b,a%b);}
template<typename T>inline T lcm(T a,T b) {if(a<0)return lcm(-a,b);if(b<0)return lcm(a,-b);return a*(b/gcd(a,b));}
int main()
{
//    fast;
    LL i,j,k,n,m,l,s=0,x,y,tc=1,p,q,a,b,c=0;
    bool f=0,ff=0;
    string st;
    char ch;
    while(cin>>n)
    {
        vi v;
        s=0;
        rep(i,n)
        {
            vp(v,x);
            s+=x;
        }
        x=ceil((s*1.0)/n);
        y=s/n;
        s=c=0;
        rep(i,n)
        {
            s+=((v[i]-x)*(v[i]-x));
            c+=(v[i]-y)*(v[i]-y);
        }
        s=min(s,c);
        cout<<s<<en;
    }
}




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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ll          long long
#define pb          push_back
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define rs(v,n)     v.resize(n)
#define hell        1000000007
#define peak        9123372036854775807
#define pii         acos(-1)
#define clr(a,x)    memset(a,x,sizeof(a))
#define ios         ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
template<typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<class x,class y> x sum(x a,y b){return a+b;}
template<class x,class y> x mul(x a,y b){return a*b;}
template<class x,class y> x sub(x a,y b){return a-b;}
template<class x,class y> x divi(x a,y b){return a/b;}

template<class x,class y>
istream &operator>>(istream &in,pair<x,y> &p) 
{ 
    in>>p.F>>p.S;
    return in;
}
template<class x>
istream &operator>>(istream &in,vector<x> &v) 
{
    for(auto& i:v)
        in>>i;
    return in;
}
template<class x,class y>
ostream &operator<<(ostream &out,pair<x,y> &p) 
{ 
    out<<"("<<p.F<<","<<p.S<<") ";
    return out; 
}
template<class x>
ostream &operator<<(ostream &out,vector<x> &v) 
{ 
    out<<v.size()<<endl;
    for(auto i:v)
        out<<i<<" ";
    out<<endl;
    return out; 
}
#define N  1000005

int main()
{
    ios;
    ll tt=1;
    // cin>>tt;
    while(tt--)
    {
    	ll i,j,k,l,m,n;
    	cin>>n;
    	vi v(n+1);
    	vector<pair<ll,ll>> vv;
    	for(i=1;i<=n;i++)
    	{
    		cin>>v[i];
    		vv.pb({v[i],i});
    	}
    	vi dp(n+5,0),dp1;
    	sort(all(vv));
    	reverse(all(vv));
    	dp1=dp;
    	for(i=0;i<n;i++)
    	{
    		ll x=n-i;
    		dp1[0]=dp[0]+vv[i].F*(abs(vv[i].S-x));
    		ll y=i+1;
    		dp1[i+1]=dp[i]+vv[i].F*(abs(vv[i].S-y));
    		for(j=1;j<=i;j++)
    		{
    			ll x=j;
	    		x=dp[j-1]+vv[i].F*(abs(vv[i].S-x));
	    		ll y=n-(i-j);
	    		y=dp[j]+vv[i].F*(abs(vv[i].S-y));
	    		dp1[j]=max(x,y);
    		}
    		dp=dp1;
    		// cout<<dp;
    	}
    	ll ans=0;
    	for(i=0;i<=n;i++)
    		ans=max(ans,dp[i]);
    	cout<<ans;
    }
    return 0;
}

Measured memory_bytes: 3776
n = input()
b = input()
n = int(n)
b = b.split()
b = [int(x) for x in b]
a = [0 for i in range(n+1)]
b = [1000001]+b+[1000001]
for i in range(n):
    a[i]=min(b[i],b[i+1])

output = sum(a)
print(output)


Measured memory_bytes: 3060
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <cmath>   
#include<cctype>
#include<string>
#include<set>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include <deque>
#include <typeinfo>
#include <utility> 
#define all(x) (x).begin(),(x).end()
#define rep(i,m,n) for(int i = m;i < n;++i)
using namespace std;
using ll = long long;
using R = double;
const ll inf = 1LL << 50;
const ll MOD = 1e9 + 7;

int n;
string s[101010];


int main() {
	cin >> n;
	string tempstr;
	cin >> tempstr;
	rep(i, 0, n) {
		s[i] = tempstr[i];
	}
	string t[2] = {"S","W"};
	rep(i, 0, 2)rep(j, 0, 2) {
		vector<string>temp(n);
		temp[0] = t[i];
		temp[n - 1] = t[j];
		map<vector<string>, string>mp;
		mp[{"W", "W", "o"}] = "S";
		mp[{"S", "W", "o"}] = "W";
		mp[{"W", "S", "o"}] = "W";
		mp[{"S", "S", "o"}] = "S";
		mp[{"W", "W", "x"}] = "W";
		mp[{"S", "W", "x"}] = "S";
		mp[{"W", "S", "x"}] = "S";
		mp[{"S", "S", "x"}] = "W";
		for (int k = 0; k < n-2 ; k++) {
			vector<string>v;
			if (k != 0) {
				v.push_back(temp[k-1]);
				v.push_back(temp[k]);
				v.push_back(s[k]);
				temp[k + 1] = mp[v];
			}
			else {
				v.push_back(temp[n - 1]);
				v.push_back(temp[0]);
				v.push_back(s[0]);
				temp[1] = mp[v];
			}
		}
		if (mp[{temp[n - 3], temp[n - 2], s[n - 2]}] == temp[n - 1]) {
			bool ok = 0;
			if (temp[n-1]=="W") {
				if ((s[n-1]=="o" && temp[n-2]!=temp[0])||(s[n-1]=="x" && temp[n-2]==temp[0])) {
					ok = 1;
				}
			}
			else {
				if ((s[n - 1] == "o" && temp[n - 2] == temp[0]) || (s[n - 1] == "x" && temp[n - 2] != temp[0])) {
					ok = 1;
				}
			}
			if (ok) {
				rep(i, 0, n) {
					cout << temp[i];
				}
				cout << endl;
				exit(0);
			}
		}
	}

	cout << "-1" << endl;
	
	return 0;
}

Measured memory_bytes: 6768
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#include <set>
#include <limits.h>
#include <queue>

#define rep(i,N) for(int (i)=0;(i)<(N);(i)++)
#define MOD 1000000007

using ll = long long;

using namespace std;

ll pow_mod(ll a, ll b, ll p) {
	if (b == 0)return 1;
	else if (b % 2 == 0)return (pow_mod(a*a, b / 2, p) % p);
	else return (pow_mod(a, b - 1, p)*a%p);
}

ll sum_digit(ll N) {
	int ans = 0;
	for (; N != 0;) {
		ans += N % 10;
		N /= 10;
	}
	return ans;
}

ll gcd(ll a,ll b) {
	if (!b)return a;
	return gcd(b, a%b);
}

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

int N, X;
int x[100100];

int main(){
	scanf("%d %d", &N, &X);
	rep(i, N)scanf("%d", &x[i]);
	ll ans = abs(x[0] - X);
	for (int i = 1; i < N; i++) {
		ans = gcd(ans, abs(x[i] - X));
	}
	printf("%lld", ans);
	return 0;
}

Measured memory_bytes: 640
import java.util.*;
class Main
{
    public static void main (String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt(), b = sc.nextInt();
        int ans = 0;
        for(int i = a; i <= b; i++){
            int v = i % 10;
            int w = (i - v) / 10 % 10;
            int x = (i - w - v)  / 100 % 10;
            int y = (i - x - w - v) / 1000 % 10;
            int z = (i - y - x - w - v) / 10000 % 10;
            if(v == z && w == y) ans++;
        }
        System.out.println(ans);
    }
}

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

#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n)-1; i >= 0; i--)

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

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

const long long INF = 1LL << 60;

// 入力
int N;
long long h[100010];

// DP テーブル
long long dp[100010];

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

  for (int i = 0; i < N; ++i) cin >> h[i];

  // 初期化 (最小化問題なので INF に初期化)
  for (int i = 0; i < 100010; ++i) dp[i] = INF;

  // 初期条件
  dp[0] = 0;

  // ループ
  for (int i = 0; i < N; ++i) {
    for (int j = 1; j <= K; j++) {
      chmin(dp[i + j], dp[i] + abs(h[i] - h[i + j]));
    }
  }

  // 答え
  cout << dp[N - 1] << endl;
}

Measured memory_bytes: 1792
while True:
    x, y = [int(x) for x in input().split()]
    if x == 0 and y == 0:
        break
    
    c = 0
    if y > x:
        x,y = y, x
    while True:
        c += 1
        x = x % y
        x,y = y,x
        if y == 0:
            break
    
    print(x,c)


Measured memory_bytes: 5608
N, M, K = map(int, input().split())
MOD = 998244353

ans = 0

class combination():
    def __init__(self, n):
        self.fact = [1] * (n+1)
        self.ifact = [1] * (n+1)
        for i in range(1, n+1):
            self.fact[i] = self.fact[i-1]*i % MOD
        self.ifact[n] = pow(self.fact[n], MOD-2, MOD)
        for i in range(n, 0, -1):
            self.ifact[i-1] = self.ifact[i]*i % MOD
    def comb(self, n, k):
        if k < 0 or k > n: return 0
        comb = self.fact[n]*self.ifact[k]*self.ifact[n-k] %MOD
        return comb
comb = combination(N)

  
for k in range(K+1):
  # M x (N-1)Ck x (M-1) ^ (N - 1 - k)
  ans += (comb.comb(N-1, k) * pow(M-1, N-1-k, MOD)) % MOD
  
print(ans * M % MOD)

Measured memory_bytes: 24688
#include<bits/stdc++.h>
#define pi 2*acos(0.0)
using namespace std;
typedef long long unsigned ll;
int main(){

   ll a,b,s=0;
   cin>>a>>b;
   while(b--)
   {
      ll c;
      cin>>c;
      s+=c;
   }
  if(a>=s)
      cout<<a-s<<endl;
  else
      cout<<"-1"<<endl;
}


Measured memory_bytes: 3672
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mp make_pair
ll bg = 1000000007;
#define ff(i,n) for(i=0;i<n;i++) 
int main()
{
    ll t;
    t = 1;
    while(t--)
    {
    	ll i,n,a,b,x,t;
		cin>>n>>x>>t;
		ll s=n/x;
		if(n%x!=0)
			s++;
		ll kk = t*s;
		cout<<kk;	    
    }
    return 0;
} 

Measured memory_bytes: 3636
n, m = map(int, input().split())
list_a = list(map(int, input().split()))

t = 0
s = sum(x for x in list_a)

for i in list_a:
    if i/s >= 1/(4*m):
        t += 1

if t >= m:
    print('Yes')
else:   print('No')

Measured memory_bytes: 3060
use std::cmp::Ordering;

fn read<T: std::str::FromStr>(
    stdin_lock: &mut std::io::StdinLock,
    buf: &mut Vec<u8>,
    delimiter: u8,
) -> T {
    buf.clear();
    let l = std::io::BufRead::read_until(stdin_lock, delimiter, buf).unwrap();
    buf.truncate(l - 1); // remove delimiter
    let s = unsafe { std::str::from_utf8_unchecked(&buf) };
    s.parse().unwrap_or_else(|_| panic!("read"))
}

fn main() {
    let stdin = std::io::stdin();
    let mut stdin_lock = stdin.lock();
    let mut buf: Vec<u8> = Vec::new();
    let _: usize = read(&mut stdin_lock, &mut buf, b' ');
    let m: usize = read(&mut stdin_lock, &mut buf, b'\n');
    let mut pyv = vec![(0i32, 0i32, 0i32); m];
    for i in 0..m {
        pyv[i].0 = i as i32;
        pyv[i].1 = read(&mut stdin_lock, &mut buf, b' ');
        pyv[i].2 = read(&mut stdin_lock, &mut buf, b'\n');
    }

    pyv.sort_by(|&(_, p1, y1), &(_, p2, y2)| match p1.cmp(&p2) {
        Ordering::Less => Ordering::Less,
        Ordering::Greater => Ordering::Greater,
        Ordering::Equal => y1.cmp(&y2),
    });

    let mut p = pyv[0].1;
    let mut c = 0;
    for i in 0..m {
        c = if p != pyv[i].1 { 1 } else { c + 1 };
        p = pyv[i].1;
        pyv[i].2 = c;
    }

    pyv.sort();
    for i in 0..m {
        println!("{:06}{:06}", pyv[i].1, pyv[i].2);
    }
}


Measured memory_bytes: 7676
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
int main() {
	int n, k, ans = 0;
	cin >> n >> k;
	for (int i = 1; i < n; i *= k) {
		if (k * i <= n)ans++;
	}
	cout << ans + 1 << endl;
	return 0;
}

Measured memory_bytes: 256
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
  
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
  
using namespace std;
  
typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;
  
const int INF=1<<29;
const double EPS=1e-9;
  
const int dx[]={1,0,-1,0,1,1,-1,-1},dy[]={0,-1,0,1,1,-1,-1,1};


int main() {
  char c;
  cin >> c;
  if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
    cout << "vowel" << endl;
  } else {
    cout << "consonant" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <cmath>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#define rep(i,n) for (int i=0;i<n;i++)
using ll = long long;
using namespace std;


void solve(){

}
int main (){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    int q;
    q = n - (n/10)*10;
    if (q == 3){
        cout << "bon" << endl;

    }
    else if (q == 0 || q == 1 || q == 6 || q == 8 ){
        cout << "pon";

    }
    else {
        cout << "hon";
        
    }

    return 0;
}

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

vector<int> v[100001],sol(100001,-1);


int lpath(int i)
{
    if(sol[i]!=-1)
        return sol[i];
    int ans=0;
    //for(int j=0;j<v.size();i++)
    //int j=v[i];
    for(int j=0;j<v[i].size();j++)
        ans=max(ans,lpath(v[i][j])+1);
    return sol[i]=ans;
}

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int t1,t2;
        cin>>t1>>t2;
        v[t1].push_back(t2);
    }
    int lp=0;
    for(int i=1;i<=n;i++)
    {
        lp=max(lp,lpath(i));
    }
    cout<<lp;
    return 0;
}


Measured memory_bytes: 8192
#include<stdio.h>
#include<stdlib.h>

int main(void){
 
  int N;
 
  int A[1000];
 
  scanf("%d\n",&N);
  
  int i,j;
  
  for(i=0;i<N;i++){
  	scanf("%d ",&A[i]);
  }
  
  int y=1;
  
  for(i=0;i<N;i++){
  
  	if(A[i]%2==0){
    	if(A[i]%3!=0&&A[i]%5!=0){
        	y=0;
        }
    }
  
  }
  
  if(y==1){
  
    printf("APPROVED\n");
  
  }else{
  
  
    printf("DENIED\n");

  
  }
  
  return 0;
  
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &x)
{
	x=0;int f=1;char c=getchar();
	for(;c>'9'||c<'0';c=getchar())if(c=='-')f=-1;
	for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);
	x*=f;
}
template <typename T> inline void print(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) print(x/10);
	putchar(x%10+48);
}
long long a1[10101010];
bool flag[10101010];
long long n,a,ans;
int main()
{
	read(n);
	for(int i=1;i<=n;i++)
	{
		read(a1[i]);		
	}
	for(int i=1;i<=n;i++)
	{
		if(a1[1]<a1[i])
		{
			a=1;
			break;
		}
		else if(a1[1]>a1[i])
		{
			a=2;
			break;
		}
	}
	if(a==0)
	{
		printf("1");
		return 0;
	}
	for(int i=2;i<=n;i++)
	{	
		if(a==2)
		{
			if(a1[i]>a1[i-1]&&flag[i-1]==false)
			{
				for(int j=i;j<=n;j++)
				{
					if(a1[i]<a1[j])
					{
						a=1;
						break;
					}
					else if(a1[i]>a1[j])
					{
						a=2;
						break;
					}
				}
				ans++;
				flag[i-1]=true;
			}
			if(a1[i]<a1[i-1])
			{
				a=2;				
			}
		}
		else if(a==1)
		{
			if(a1[i]>a1[i-1])
			{
				a=1;				
			}
			if(a1[i]<a1[i-1]&&flag[i-1]==false)
			{
				for(int j=i;j<=n;j++)
				{
					if(a1[i]<a1[j])
					{
						a=1;
						break;
					}
					else if(a1[i]>a1[j])
					{
						a=2;
						break;
					}
				}
				ans++;
				flag[i-1]=true;
			}
		}
	}
	print(ans+1);
	return 0;
}

Measured memory_bytes: 4480
#define _CRT_SECURE_NO_WARNINGS
#include"bits/stdc++.h"
#ifdef _DEBUG
#define DBG(n) n
#else
#define DBG(n)
#endif
#define INF         1e9
#define INFLL       1e18
#define EPS         1e-9
#define REP(i,n)    for(ll i=0,i##_len=(n);i<i##_len;++i)
#define REP1(i,n)   for(ll i=1,i##_len=(n);i<=i##_len;++i)
#define REPR(i,n)   for(ll i=(n)-1;i>=0;--i)
#define REPR1(i,n)  for(ll i=(n);i>0;--i)
#define REPC(i,obj) for(auto i:obj)
#define ALL(obj)    (obj).begin(),(obj).end()
#define SETP(n)     cout<<fixed<<setprecision(n)
using namespace std;
using ll = long long;
template<typename T = ll>inline T in() { T ret; cin >> ret; return ret; }

signed main()
{
	ll d, w, h;
	while (cin >> d >> w >> h, d) {
		ll minr = min({ hypot(d,w),hypot(w,h),hypot(h,d) }) / 2;
		ll n = in();
		REP(i, n) {
			ll r = in();
			cout << (r > minr ? "OK" : "NA") << endl;
		}
	}
}


Measured memory_bytes: 2996
#include<bits/stdc++.h>
#include<tuple>
#define INF  (int)1e8
#define EPS   1e-9
#define MOD 1000000007
#define Pi 3.14159
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define rep(i,a,n) for (int i=a;i<n;i++)
#define repk(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define setBit(S, j) (S |= (1 << j))
#define clearBit(S, j) (S &= ~(1 << j))
#define toggleBit(S, j) (S ^= (1 << j))
#define IN(x,n)   for(int e=0;e<n;e++){ll y;cin>>y;x.pb(y);}
#define print(x)    for(auto it:x) cout<<it<<' '; cout<<endl;
#define printPI(x)  for(auto it:x) cout<<it.F<<' '<<it.S<<'\t';  cout<<endl;
#define ll long long
#define PI pair<int,int>
#define PL pair<ll,ll>
#define vi vector<int>
#define vb vector<bool>
#define vl vector<ll>
#define vvi vector<vi>
#define vvl vector<vl>
#define vvvi vector<vvi>
#define vvvl vector<vvl>
#define vpi vector<pi>
#define vpl vector<pl>
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define F first
#define S second
#define uset unordered_set
#define umap unordered_map
#define all(x) x.begin(), x.end()
#define dbg(x, y) cout << x << " = " << y << endl
using namespace std;

const int N = 1e5 + 5;
ll gcd(ll a, ll b) {ll temp; while (b > 0) {temp = a % b; a = b; b = temp;} return a;}
ll lcm(ll a, ll b) {return a * b / gcd(a, b);}
ll fpow(ll  b, ll exp, ll mod) {if (exp == 0) return 1; ll t = fpow(b, exp / 2, mod); if (exp & 1) return t * t % mod * b % mod; return t * t % mod;}
ll divmod(ll i, ll j, ll mod) {i %= mod, j %= mod; return i * fpow(j, mod - 2, mod) % mod;}


void sol() {

	string n; cin >> n;
	int64_t s = 0;
	for (char k : n)
		s += (k - '0');
	string cnt = "Yes";
	if (s % 9 != 0)
		cnt = "No";
	cout << cnt;


}

int main() {
	// fio
	int t = 1;
	// cin >> t;
	while (t--)
		sol();

	return 0;
}



Measured memory_bytes: 3740
#include <iostream>
#include <algorithm>
#include <vector> //動的配列
#include <string>
#include <list> //双方向リスト
#include <map> //連想配列
#include <set> //集合
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <bitset>


//小さい順から取り出すヒープ
//priority_queue<ll, vector<ll>, greater<ll> > pque1;

typedef long long ll;


using namespace std;

typedef pair<int, ll> P;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)



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

template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}

const int  max_v=1e5+10;

int main(){
    int n;
    ll w;
    cin>>n>>w;
    vector<P> vec(n);
    rep(i,n){
        P p;
        cin>>p.first>>p.second;
        vec[i]=p;
        //cout<<vec[i].first<<endl;
    }
    ll dp[n+1][max_v];
    ll inf=1e10;
    fill(dp[0],dp[n+1],inf);
    dp[0][0]=0;
    for (int i=1;i<=n;i++){
        for (int j=0;j<max_v;j++){
            if (dp[i-1][j]==inf) continue;
            if (dp[i-1][j]!=inf && dp[i-1][j]+vec[i-1].first<=w) {
                dp[i][j+vec[i-1].second]=min(dp[i][j+vec[i-1].second],dp[i-1][j]+vec[i-1].first);
            } 
            dp[i][j]=min(dp[i-1][j],dp[i][j]);
            //cout<<dp[i][j+vec[i-1].second]<<' '<<i<<' '<<j;
        }
    }
    for (int j=max_v-1;j>=0;j--){
        if (dp[n][j]!=inf) {
            cout<<j;
            break;
        }
    }
}


Measured memory_bytes: 79104
using System;
using System.Linq;
using System.Collections.Generic;

using E = System.Linq.Enumerable;

public class Program
{
    public static void Main()
    {
        var ab = Console.ReadLine().Split().ToArray();
        var (a, b) = (long.Parse(ab[0]), long.Parse(ab[1].Replace(".", "")));

        var c = a * b / 100;

        Console.WriteLine(c);
    }
}


Measured memory_bytes: 27968
import math
from bisect import bisect
x1,y1,x2,y2 = map(int,input().split())
N = int(input())
src = [tuple(map(int,input().split())) for i in range(N)]
src.sort()
if x1 > x2:
    x1,x2 = x2,x1
    y1,y2 = y2,y1

arc = 5 * math.pi

if x1 == x2:
    if y1 > y2:
        y1,y2 = y2,y1
    ans = 100 * (y2-y1)
    for x,y in src:
        if x == x1 and y1 < y < y2:
            ans += arc*2 - 20
            break
    print(ans)
    exit()

if y1 == y2:
    if x1 > x2:
        x1,x2 = x2,x1
    ans = 100 * (x2-x1)
    for x,y in src:
        if y == y1 and x1 < x < x2:
            ans += arc*2 - 20
            break
    print(ans)
    exit()

if y1 < y2:
    lis = []
    for x,y in src:
        if x < x1: continue
        if x > x2: break
        if not y1 <= y <= y2: continue
        i = bisect(lis, y)
        if i == len(lis):
            lis.append(y)
        else:
            lis[i] = y
    ans = 100 * (x2-x1 + y2-y1)
    if len(lis) in (x2-x1+1, y2-y1+1):
        ans += (len(lis)-1) * (arc - 20)
        ans += arc*2 - 20
    else:
        ans += len(lis) * (arc - 20)
    print(ans)
else:
    lds = []
    for x,y in src:
        if x < x1: continue
        if x > x2: break
        if not y2 <= y <= y1: continue
        i = bisect(lds, -y)
        if i == len(lds):
            lds.append(-y)
        else:
            lds[i] = -y
    ans = 100 * (x2-x1 + y1-y2)
    if len(lds) in (x2-x1+1, y1-y2+1):
        ans += (len(lds)-1) * (arc - 20)
        ans += arc*2 - 20
    else:
        ans += len(lds) * (arc - 20)
    print(ans)

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

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

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
#define endl "\n"
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();
// freopen("input.txt", "r", stdin);

ll power(ll x, ll pw, ll mod) {
    ll res = 1;
    x = x % mod;  // if it x >= p
    while (pw > 0) {
        if (pw & 1)
            res = (res*x) % mod;
        pw /= 2;
        x = (x*x) % mod;
    }
    return res;
}
ll modInverse(ll n, ll p) {
    return power(n, p-2, p) % p; // Fermat's little theorem
}
ll nCr(ll n, ll m, ll mod=1e9+7) {
    m = min(m, n-m);
    if (m == 0) return 1;
    ll num = 1, dem = 1;
    for(ll i = 1; i <= m; i++) {
        num = (num*(n+1-i)) % mod;
        dem = (dem*(i)) % mod;
    }
    return (num * modInverse(dem, mod)) % mod;
}


int main() {
    ll S;
    cin >> S;
    ll mod = 1e9 + 7;
    // X1 + ...+ Xn = r
    // H(n, r) = C(r+n-1, n-1);
    int sel = 1;
    ll ans = 0;
    while(S-sel*3 >= 0) {
        ll n = sel;
        ll r = S-sel*3;
        ans += nCr(r+n-1, n-1);
        ans %= mod;
        sel += 1;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3628
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!{
        d: usize
    }
    println!("{}", match d {
        25 => "Christmas".to_string(),
        24 => "Christmas Eve".to_string(),
        23 => "Christmas Eve Eve".to_string(),
        22 => "Christmas Eve Eve Eve".to_string(),
        _ => unreachable!()
    });
}


Measured memory_bytes: 4352
#!/usr/bin/python3

"""
https://atcoder.jp/contests/abc176/tasks/abc176_a
Takoyaki
"""

import math

def solve(n, x, t):
    return int(math.ceil(n / x)) * t

if __name__ == "__main__":
    n, x, t = list(map(int, input().split()))
    print(solve(n, x, t))



Measured memory_bytes: 9164
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define rep(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define reps(i, n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
#define rrep(i, n) for(int i=((int)(n)-1); i>=0; --i)
#define rreps(i, n) for(int i=((int)(n)); i>0; --i)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define pl(s) cout << (s) << "\n";
#define pls(...) {bool space = false; for(auto i : __VA_ARGS__) (cout << (space?" ":"") << i), space = true; cout << "\n";}
#define plexit(s) {cout << (s) << "\n"; exit(0);}
#define yes(s) cout << ((s)?"Yes":"No") << "\n";
#ifdef __LOCAL
#include <dump.hpp>
#define dump(...) DUMPOUT << "  " << string(#__VA_ARGS__) << ": " << "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]" << endl << "    ", dump_func(__VA_ARGS__)
#else
#define dump(...)
#endif
template<typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
struct IOInit { IOInit() { cin.tie(nullptr); ios::sync_with_stdio(false); dump("READY"); /*cout << unitbuf;*/} } IO_INIT;
using ll = long long; using ull = unsigned long long; using ld = long double;
template<typename T = int> using V = vector<T>; template<typename T = int> using P = pair<T, T>;
using Vi = V<int>; using Vl = V<ll>; using Vd = V<ld>; using VVi = V<Vi>; using VVl = V<Vl>; using Pi = P<int>; using Pl = P<ll>; using Pd = P<ld>;
constexpr ll MOD = 1000000007; constexpr int INF = (1 << 30) - 1; constexpr ll INFL = 1LL << 60; constexpr ld EPS = 1e-12; constexpr ld PI = 3.141592653589793238462643383279;

using mint = modint998244353;

struct S { mint a; int size; };
struct F { mint a, b; };
S op(S l, S r) { return S{l.a + r.a, l.size + r.size}; }
S e() { return S{0, 0}; }
S mapping(F l, S r) { return S{r.a * l.a + r.size * l.b, r.size}; }
F composition(F l, F r) { return F{r.a * l.a, r.b * l.a + l.b}; }
F id() { return F{1, 0}; }

signed main(void) {
  int n, q; cin >> n >> q;
  V<S> a(n);
  rep(i,n) {
    int x; cin >> x;
    a[i] = S{x, 1};
  }

  lazy_segtree<S, op, e, F, mapping, composition, id> seg(a);

  rep(i,q) {
    int t; cin >> t;
    if (t == 0) {
      int l, r, c, d; cin >> l >> r >> c >> d;
      seg.apply(l, r, F{c, d});
    } else {
      int l, r; cin >> l >> r;
      pl(seg.prod(l, r).a.val());
    }
  }
  return 0;
}


Measured memory_bytes: 19316
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<functional>
#include<cstdio>
#include<cstdlib>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
//#define MOD 998244353
#define LINF (long long)4e18
#define jck 3.141592

const double EPS = 1e-10;

using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;

int n,m,q;
vector<int> a,b,c,d;
int ans = 0;

void dfs(vector<int> v){
    if(v.size() == n){
        int now = 0;
        rep(i,q){
            if(v[b[i]]-v[a[i]] == c[i]){
                now += d[i];
            } 
        }
        ans = max(ans,now);
        return;
    }
    if(v.size() == 0){
        repr(i,1,m+1){
            v.push_back(i);
            dfs(v);
            v.pop_back();
        }
    }
    else{
        int k = v.size();
        int d = v[k-1];
        repr(i,d,m+1){
            v.push_back(i);
            dfs(v);
            v.pop_back();
        }
    }
}

int main(){
    cin >> n >> m >> q;
    a.resize(q);
    b.resize(q);
    c.resize(q);
    d.resize(q);
    rep(i,q){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        a[i]--;
        b[i]--;
    }
    vector<int> v;
    dfs(v);
    cout << ans << endl;
}



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

const int N = 200005;
int n, fa[N], mx[N][2], st[N], ed[N], dfs_clock, ans[N];
vector<int> g[N], vmx[N][2];

void dfs(int u) {
	st[u] = ++dfs_clock;
	for (int i = 0; i < 2; ++i)
		vmx[mx[u][i]][i].push_back(dfs_clock);
	for (int v : g[u])
		if (v != fa[u]) {
			fa[v] = u;
			if (v > mx[u][0])
				mx[v][0] = v, mx[v][1] = mx[u][0];
			else
				mx[v][0] = mx[u][0], mx[v][1] = max(v, mx[u][1]);
			dfs(v);
		}
	ed[u] = dfs_clock;
}
int query(const vector<int> &v, int t) {
	return upper_bound(v.begin(), v.end(), ed[t]) - lower_bound(v.begin(), v.end(), st[t]);
}

void solve(int u) {
	for (int v : g[u])
		if (v != fa[u]) {
			if (v > mx[fa[u]][0])
				ans[v] = ans[u] + query(vmx[mx[u][0]][v > mx[u][0]], v);
			else
				ans[v] = ans[u] + (u > mx[fa[u]][0] ? query(vmx[u][0], v) - query(vmx[mx[fa[u]][0]][1], v) : 0);
			solve(v);
		}
}

int main() {
	scanf("%d", &n);
	for (int i = 1, u, v; i < n; ++i) {
		scanf("%d%d", &u, &v);
		g[u].push_back(v), g[v].push_back(u);
	}
	mx[1][0] = 1, dfs(1);
	solve(1);
	for (int i = 2; i <= n; ++i)
		printf("%d%c", ans[i], " \n"[i == n]);
	return 0;
}


Measured memory_bytes: 44012
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>


using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD (ll)1000000007
#define P pair<ll, ll>

ll n, s[2100], ans;
int main() {
	cin >> n;
	REP(i, n)cin >> s[i];
	sort(s, s + n);
	REP(i, n) {
		FOR(j, i + 1, n) {
			FOR(k, j + 1, n) {
				if (s[i] + s[j] <= s[k])break;
				ans++;
			}
		}
	}
	cout << ans << endl;
}


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

using namespace std;

int Max = 1e9+7;

vector<int> g[100010];
int dp[100010];

int get(int u) {

    if (dp[u] != -1) {
        return dp[u];
    }
    int ans = 0;
    for (int i = 0; i < g[u].size(); ++i) {
        int v = g[u][i];
        ans = max (ans, 1 + get(v));
    }

    dp[u] = ans;
    return dp[u];
}

int main(void) {
    
    int n, m;
    cin>>n>>m;
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin>>a>>b;
        --a, --b;
        g[b].push_back(a);
    }
    memset(dp, -1, sizeof(dp));
    int ans = 0;
    for(int i = 0; i < n; ++i) {
        ans = max(ans, get(i));
    }

    cout<<ans;

    return 0;
}



Measured memory_bytes: 10624
# -*- coding: utf-8 -*-

import sys
import os


N, M = list(map(int, input().split()))
students = []
checkpoints = []

for i in range(N):
    a, b = list(map(int, input().split()))
    students.append([a, b])

for i in range(M):
    a, b = list(map(int, input().split()))
    checkpoints.append([a, b])

for student in students:
    min_dist = float('inf')
    min_i = None
    for i, checkpoint in enumerate(checkpoints):
        manhattan_dist = abs(checkpoint[0] - student[0]) + abs(checkpoint[1] - student[1])
        if manhattan_dist < min_dist:
            min_dist = manhattan_dist
            min_i = i
    print(min_i + 1)


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

using namespace std;


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    long long a,b,c,k;
    while(cin>>a>>b>>c>>k){
        if(k%2==0){
            cout<<a-b<<endl;
        }
        else {
            cout<<b-a<<endl;
        }
    }
return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define debug(x) cout << '>' << #x << ':' << x << endl;
#define ll long long
int arr[60];
int n, p;

int main() {

	scanf("%d%d", &n, &p);
	ll ans = 0, odd = 0;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		if (arr[i] & 1)
			odd++;
	}
	ans = (odd == 0 ? ((p == 1) ? 0 :( 1LL << n)) : (1LL << (n-1)));
	cout << ans;
}


Measured memory_bytes: 3620
import sys
h,w = map(int, input().split())
grid = [list(input()) for _ in range(h)]

dx = [-1,1,0,0]
dy = [0,0,-1,1]

for i,row in enumerate(grid):
    for j in range(w):
        if grid[i][j] == "#":
            for k in range(4):
                nx = j + dx[k]
                ny = i + dy[k]            
                if (nx < 0) or (w-1 < nx) or (ny < 0) or (h-1 < ny):
                    continue
                elif grid[ny][nx] == "#":
                    break
                else:
                    pass
            else:
                print("No")
                sys.exit()
else:
    print("Yes")

Measured memory_bytes: 9220
#include<bits/stdc++.h>
using namespace std;
const int N=6005,mod=1000000007;
inline void add(int &a,int b){a+=b;if(a>=mod)a-=mod;}
int n,m,dp[2][N][2];
int main()
{
	scanf("%d%d",&n,&m);
	dp[0][0][1]=1;
	for(int i=1;i<=n;i++)
		dp[0][i][0]=1;
	int p=0;
	for(int i=0;i<2*m;i++)
	{
		memset(dp[p^1],0,sizeof(dp[p^1]));
		for(int j=0;j<=n;j++)
		{
			for(int s=0;s<2;s++)
			{
				int x=j,y=n-j+(i%2);
				if(!dp[p][j][s])
					continue;
				if(x) add(dp[p^1][j-1+(i+1)%2][s|(j==1)],dp[p][j][s]);
				if(y) add(dp[p^1][j+(i+1)%2][s],dp[p][j][s]);
			}
		}
		p^=1;
	}
	int ans=0;
	for(int i=0;i<=n;i++)
		add(ans,dp[p][i][1]);
	printf("%d\n",ans);
	return 0;
}

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

int main() {
    ll N;
    cin >> N;
    vector<ll> A(N);
    vector<ll> A_;
    rep(i, N) { cin >> A[i]; }
    bool flg = A[0] < A[1];
    A_.push_back(A[0]);
    rep(i, N - 2) {
        if (A[i + 1] == A[i + 2]) {
            continue;
        }
        bool flg_tmp = A[i + 1] < A[i + 2];
        if (flg != flg_tmp) {
            A_.push_back(A[i + 1]);
        }
        flg = flg_tmp;
    }
    A_.push_back(A[N - 1]);

    ll n = A_.size();
    ll ans = 1000;
    rep(i, n - 1) {
        if (A_[i] < A_[i + 1]) {
            ans += (ans / A_[i]) * (A_[i + 1] - A_[i]);
        }
    }
    cout << ans << endl;

    return 0;
}


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

int main(){
  string S;
  cin>>S;
  int K;
  cin>>K;

  int N=S.size();
  vector<vector<int64_t>> dp0(N+1,vector<int64_t>(4,0));
  vector<vector<int64_t>> dp1(N+1,vector<int64_t>(4,0));
  //初期値
  dp0[0][0]=1;
  for(int i=1;i<N;++i) dp0[i][0]=0;
  dp1[0][0]=0;
  for(int i=1;i<N;++i) dp1[i][0]=1;
  


  for(int i=0;i<N;++i){
    for(int j=1;j<=K;++j){
      int a=S[i]-'0';
      if(a==0){
        dp0[i+1][j]=dp0[i][j];
        dp1[i+1][j]=9*dp1[i][j-1]+dp1[i][j];
      }
      else{
        dp0[i+1][j]=dp0[i][j-1];
        dp1[i+1][j]=(a-1)*dp0[i][j-1]+dp0[i][j]+9*dp1[i][j-1]+dp1[i][j];
      }
    }
  }

  cout<<dp0[N][K]+dp1[N][K]<<endl;
}


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

int main()
{
    // 整数の入力
    int A,B,C,K;

    cin >> A >> B >> C >> K;
    
    int ans = 0;
    if(K <= A){
        ans = K;
    }else if(K <= A+B){
        ans = A;
    }else{
        ans = 2*A+B-K;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

vector<string> split(const string &s, char delim) {
  vector<string> elems;
  string item;
  for (char ch: s) {
    if (ch == delim) {
      if (!item.empty()) {
        elems.push_back(item);
      }
      item.clear();
    }
    else {
      item += ch;
    }
  }
  if (!item.empty()) {
    elems.push_back(item);
  }
  return elems;
}

string to_str_with_zero(int i, int w) {
  ostringstream sout;
  sout << std::setfill('0') << std::setw(w) << i;
  string s = sout.str();
  return s;
}

int letter_to_int(char c) {
  return tolower(c) - 'a';
}

int compare_array(vector<int> a1, vector<int>a2) {
  if (a1.size() != a2.size()) {
    return a1.size() - a2.size();
  }
  for (int i=0; i<a1.size(); i++) {
    if (a1.at(i) != a2.at(i)) {
      return a1.at(i) - a2.at(i);
    }
  }
  return 0;
}

int gcd(int a, int b) {
  if(a % b == 0) {
    return b;
  }
  return gcd(b, a % b);
}

char int_to_char(int a) {
  if (a == -1) {
    return 'z';
  }
  else {
    return 'a' + a;
  }
}

long nCr(int n, int r) {
    long ans = 1;
    for (int i = n; i > n - r; --i) {
        ans = ans*i;
    }
    for (int i = 1 ; i < r + 1; ++i) {
        ans = ans / i;
    }
    return ans;
}

long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
}

int divide_count(int a, int divider) {
  int r = 0;
  while(a % divider == 0) {
    a /= divider;
    r++;
  }
  return r;
}

bool is_prime(int a) {
  int i = 2;
  while(i * i <= a) {
    if(a % i == 0) {
      return false;
    }
    i++;
  }
  return true;
}

vector<vector<int>> all_comb(int n, int k) {
  vector<vector<int>> combs(nCr(n, k), vector<int>(k));
  for(int i=0; i<k; i++) {
    combs[0][i] = i;
    combs[1][i] = i;
  }
  
  for(long i=1; i<nCr(n, k); i++) {
    int p = 1;
    while(combs[i][k - p] == n - p) {
      p++;
      if(p > k) {
        break;
      }
    }
    combs[i][k - p]++;
    int q = combs[i][k - p];
    for(int j=1; j<p; j++) {
      combs[i][k - p + j] = q + j;
    }

    if(i < nCr(n, k) - 1) {
      for(int j=0; j<k; j++) {
        combs[i + 1][j] = combs[i][j];
      }
    }
  }

  return combs;
}

int main() {
  std::cout << std::setprecision(9);
  int n, m, q;
  cin >> n >> m >> q;

  vector<vector<int>> c(q, vector<int>(4));
  for(int i=0; i<q; i++) {
    cin >> c[i][0] >> c[i][1] >> c[i][2] >> c[i][3];
  }

  int max = 0;
  vector<int> comb(n);
  for(int i=0; i<n; i++) {
    comb[i] = 0;
  }
  while(true) {
    int score = 0;
    for(int i=0; i<q; i++) {
      if(comb[c[i][1] - 1] - comb[c[i][0] - 1] == c[i][2]) {
        score += c[i][3];
      }
    }
    if(score > max) {
      max = score;
    }

    int p = n - 1;
    while(comb[p] == m - 1) {
      p--;
      if(p < 0) {
        break;
      }
    }
    if(p < 0) {
      break;
    }
    comb[p]++;
    for(int i=p+1; i<n; i++) {
      comb[i] = comb[p];
    }
  }

  cout << max << endl;
}

Measured memory_bytes: 3596
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		long K = sc.nextLong();
		int N = 50;
		System.out.println(N);
		
		long base = N-1 + K/N - K%N;
		for(int i=0; i<N; i++)
			System.out.print((base + (i<K%N ? N : 0)) + (i==N-1 ? "\n" : " "));
		
		sc.close();
	}
}


Measured memory_bytes: 21844
#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 FI first
#define SE second
#define MP make_pair
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;
typedef pair < ll , ll > pll;

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


ll addMod(ll a, ll b){
	if(a + b >= MOD) return a + b - MOD;
	return a + b;
}

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

ll fast(ll a, ll b){
	if(b == 0) return 1;
	ll tmp = fast(a,b/2);
	tmp = mulMod(tmp,tmp);
	if(b & 1) tmp = mulMod(tmp,a);
	return tmp;
}

ll GCD(ll a, ll b){
	if(a > b) return GCD(b,a);
	if(a == 0) return b;
	return GCD(b%a,a);
}

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

const int N = 100;

int a[N + 5];

int main(){
	ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n;
	cin >> n;
	FOR(i,n) cin >> a[i];
	sort(a,a+n);
	int ans = 1;
	REP(i,1,n-1){
		if(a[i] == a[i-1]) continue;
		ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
s = input()

a_s = ["A","C","G","T"]
l=[]
for i in range(len(s)):
    if s[i] in a_s:
        l.append(1)
    else:
        l.append(0)

cnt = 0
ans = 0
for i in range(len(s)):
    if l[i] == 1:
        cnt += 1
    else:
        ans = max(cnt,ans)
        cnt = 0
ans = max(cnt,ans)
print(ans)


Measured memory_bytes: 38444
N, K, C = map(int, input().split())
S = " " + input()

L = [0 for _ in range(K+1)]
R = [0 for _ in range(K+1)]

p = 1
i = 1
while i < N+1 and p <= K:
    if S[i] == "o":
        L[p] = i
        i += C
        p += 1
    i += 1

p = K
i = N
while i > 0 and p > 0:
    if S[i] == "o":
        R[p] = i
        i -= C
        p -= 1
    i -= 1

for i in range(1, K+1):
    if L[i] == R[i]:
        print(L[i])

Measured memory_bytes: 57448
# -*- coding: utf-8 -*-
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
import copy
sys.setrecursionlimit(10**6)

# lis_of_lis = [[] for _ in range(N)]


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


def z():
    return int(sys.stdin.readline())


def S():
    return sys.stdin.readline()[:-1]


def C(line):
    return [sys.stdin.readline() for _ in range(line)]


def is_prime(n):
    if n == 1:
        return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


MOD = pow(10, 9)+7

N = z()
A = zz()
ans = 0
part_sum = [0]*N
part_sum[0] = A[0]
sum_a = sum(A) % MOD
for i in range(1, N):
    part_sum[i] = (part_sum[i-1] + A[i]) % MOD

for i in range(N - 1):
    tmp = A[i]*(sum_a - part_sum[i])
    ans = (ans+tmp) % MOD
    ans = ans % MOD
print(ans)

# for i in range(N):
#     for j in range(i + 1, N):
#         ans += A[i]*A[j]
#         ans %= MOD
# print(ans)


Measured memory_bytes: 94160
A, B, C = map(int, input().split())
K = int(input())

i = 0
# BがAより大きくなるために必要な回数
while(B<=A):
    i += 1
    B *= 2

# CがBより大きくなるために必要な回数
while(C<=B):
    i += 1
    C *= 2


    
if i <=K:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 9168