akhauriyash/Code-Regression huggingface dataset:
//made by darkfire
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#define FL "a"
using namespace std;
typedef long long ll;
typedef double dd;
const int N=2e5+10;
const ll INF=1e18;
inline ll read(){
  ll data=0,w=1;char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
  if(ch=='-')w=-1,ch=getchar();
  while(ch<='9'&&ch>='0')data=data*10+ch-48,ch=getchar();
  return data*w;
}
inline void file(){
  freopen(FL".in","r",stdin);
  freopen(FL".out","w",stdout);
}
 
int n,m;ll x[N];ll ans;
int head[N],nxt[N<<1],to[N<<1],val[N<<1],cnt;
inline void add(int u,int v,int w){
  to[++cnt]=v;val[cnt]=w;nxt[cnt]=head[u];head[u]=cnt;
}
 
struct edge{int u,v;ll w;}E[20*N];
inline bool cmp(edge a,edge b){return a.w<b.w;}
int fa[N];int find(int x){return fa[x]?fa[x]=find(fa[x]):x;}
 
ll dep[N];int Dep[N],ffa[N],siz[N],son[N],top[N];
void dfs1(int u,int ff){
  ffa[u]=ff;siz[u]=1;son[u]=0;Dep[u]=Dep[ff]+1;
  for(int i=head[u],v;i;i=nxt[i]){
    v=to[i];if(v==ff)continue;
    dep[v]=dep[u]+val[i];dfs1(v,u);
    siz[u]+=siz[v];if(siz[son[u]]<siz[v])son[u]=v;
  }
}
void dfs2(int u,int tp){
  top[u]=tp;if(son[u])dfs2(son[u],tp);
  for(int i=head[u],v;i;i=nxt[i]){
    v=to[i];if(v==ffa[u]||v==son[u])continue;
    dfs2(v,v);
  }
}
inline int lca(int u,int v){
  while(top[u]!=top[v])
    Dep[top[u]]>Dep[top[v]]?u=ffa[top[u]]:v=ffa[top[v]];
  return Dep[u]<Dep[v]?u:v;
}
inline ll dist(int u,int v){return dep[u]+dep[v]-2ll*dep[lca(u,v)];}
 
int rt,blk,sz[N],w[N],vis[N];
void getsz(int u,int ff){
  sz[u]=1;
  for(int i=head[u],v;i;i=nxt[i]){
    v=to[i];if(v==ff||vis[v])continue;
    getsz(v,u);sz[u]+=sz[v];
  }
}
void getrt(int u,int ff){
  w[u]=blk-sz[u];
  for(int i=head[u],v;i;i=nxt[i]){
    v=to[i];if(v==ff||vis[v])continue;
    getrt(v,u);w[u]=max(w[u],sz[v]);
  }
  if(w[u]<w[rt])rt=u;
}
int c;ll len[N];
void getmin(int u,int ff){
  if(len[c]+x[c]>len[u]+x[u])c=u;
  for(int i=head[u],v;i;i=nxt[i]){
    v=to[i];if(v==ff||vis[v])continue;
    len[v]=len[u]+val[i];getmin(v,u);
  }
}
void getedge(int u,int ff){
  if(u!=c)E[++m]=(edge){u,c,x[u]+x[c]+dist(u,c)};
  for(int i=head[u],v;i;i=nxt[i]){
    v=to[i];if(v==ff||vis[v])continue;
    getedge(v,u);
  }
}
inline void solve(int u){
  len[u]=0;c=u;getmin(u,0);
  getedge(u,0);vis[u]=1;
  for(int i=head[u],v;i;i=nxt[i]){
    v=to[i];if(vis[v])continue;
    getsz(v,u);rt=0;blk=sz[v];getrt(v,u);solve(rt);
  }
}
 
int main()
{
  n=read();
  for(int i=1;i<=n;i++)x[i]=read();
  for(int i=2,u,v,_w;i<=n;i++){
    u=read();v=read();_w=read();
    add(u,v,_w);add(v,u,_w);
    E[++m]=(edge){u,v,x[u]+x[v]+_w};
  }
  dfs1(1,0);dfs2(1,1);
 
  rt=0;w[0]=blk=n;len[0]=INF;
  getsz(1,0);getrt(1,0);solve(rt);
  
  sort(E+1,E+m+1,cmp);
  for(int i=1,u,v;i<=m;i++){
    u=E[i].u;v=E[i].v;
    if(find(u)!=find(v)){
      fa[find(u)]=find(v);
      ans+=E[i].w;
    }
  }
  printf("%lld\n",ans);
  return 0;
}

Measured memory_bytes: 84224
#pragma region header
#include <bits/stdc++.h>
using namespace std;

#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_CAT_I(x,y) x ## y
//#define CPP_STR(x) CPP_STR_I(x)
//#define CPP_STR_I(args...) #args
//#define ASSERT(expr...) assert((expr))

using i8 = int8_t;
using u8 = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
using f32 = float;
using f64 = double;
//using f80 = __float80;
#pragma endregion

#pragma region const
constexpr i64 INF = 1'010'000'000'000'000'017LL;
constexpr i64 MOD = 1'000'000'007LL;
constexpr f64 EPS = 1e-12;
constexpr f64 PI = 3.14159265358979323846;
#pragma endregion

#pragma region util
#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }
template<typename T, size_t N>
i64 SIZE(const T(&)[N]) { return static_cast<i64>(N); }

template<typename T, typename U, typename Comp = less<>>
bool chmax(T& xmax, const U& x, Comp comp = {}) {
	if (comp(xmax, x)) {
		xmax = x;
		return true;
	}
	return false;
}
template<typename T, typename U, typename Comp = less<>>
bool chmin(T& xmin, const U& x, Comp comp = {}) {
	if (comp(x, xmin)) {
		xmin = x;
		return true;
	}
	return false;
}
#pragma endregion

#pragma region init
struct ProconInit {
	static constexpr int IOS_PREC = 15;
	static constexpr bool AUTOFLUSH = false;

	ProconInit() {
		cin.tie(nullptr);
		ios::sync_with_stdio(false);
		cout << fixed << setprecision(IOS_PREC);
		if (AUTOFLUSH)
			cout << unitbuf;
	}
} PROCON_INIT;
#pragma endregion

int main()
{
	i64 A, B, T;
	cin >> A >> B >> T;
	cout << T / A * B << endl;
	return 0;
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);

    int n,a;
    cin>>n>>a;

    if((n%500)<=a)cout<<"Yes";
    else cout<<"No";
    return 0;
}


Measured memory_bytes: 256
#pragma region Macros

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define int ll
using vi = vector<int>;
using vvi = vector<vi>;

#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define ALL(x) (x).begin(), (x).end()
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))

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

// debug methods
// usage: debug(x,y);
#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0, a1, a2, a3, a4, x, ...) x
#define debug_1(x1) cout << #x1 << ": " << x1 << endl
#define debug_2(x1, x2) cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << endl
#define debug_3(x1, x2, x3) cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " << x3 << endl
#define debug_4(x1, x2, x3, x4) cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " << x3 << ", " #x4 << ": " << x4 << endl
#define debug_5(x1, x2, x3, x4, x5) cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " << x3 << ", " #x4 << ": " << x4 << ", " #x5 << ": " << x5 << endl
#ifdef _DEBUG
#define debug(...)                                                        \
    CHOOSE((__VA_ARGS__, debug_5, debug_4, debug_3, debug_2, debug_1, ~)) \
    (__VA_ARGS__)
#else
#define debug(...)
#endif

#pragma endregion

void Main() {
    int X;
    cin >> X;

    for (int i = 1; i < 400; i++) {
        if ((X * i) % 360 == 0) {
            cout << i;
            return;
        }
    }
}

#pragma region main
main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Main();
    cout << flush;
}
#pragma endregion


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

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int n;
	int m;
	cin >> n >> m;
	int ans = ((int)(n*(n-1)/2) + (int)(m*(m-1) / 2));

	cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define rep(X,N) for(ll X = 0; X < (N); X++)
#define PI (acos(-1.0))
#define pback push_back
#define mpair make_pair
#define MODN 1000000007
#define ALL(V) (V).begin(),(V).end()

using namespace std;

int main(){
  
    string s,t;
    cin >> s;
    cin >> t;

    int size = s.size();

    bool ans = false;

    rep(i,size - 1){
        string sfront = s.substr(0, size - 1 - i);
        string sback  = s.substr(size - 1 - i, i + 1);

        string tmps = sback + sfront;

        if(tmps == t){
            ans = true;
            break;
        }
    }

    if(s == t) ans = true;

    cout << (ans ? "Yes" : "No") << endl;

    return 0;
}


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

int main() {
    int N;
    cin >> N;
    map<string, int> mp;
    string s;
    for (int i = 0; i < N; i++) {
        cin >> s;
        mp[s]++;
    }
    int M;
    cin >> M;
    string t;
    for (int i = 0; i < M; i++) {
        cin >> t;
        mp[t]--;
    }

    int ans = 0;
    for (auto x : mp) {
        ans = max(ans, x.second);
    }

    cout << ans << endl;
}

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

namespace {

}

int main()
{
	string S;

	cin >> S;

	set<char> set1(S.begin(), S.end());

	if (set1.size() != S.size()){
		cout << "no" << endl;
	}
	else {
		cout << "yes" << endl;
	}

	return 0;
}

Measured memory_bytes: 256
full = set([i for i in range(1, 14)])
t = ['S', 'H', 'C', 'D']
c = [set() for i in range(4)]
N = int(input())
for i in range(N):
    card = input().split()
    if card[0] == 'S':
        c[0].add(int(card[1]))
    elif card[0] == 'H':
        c[1].add(int(card[1]))
    elif card[0] == 'C':
        c[2].add(int(card[1]))
    elif card[0] == 'D':
        c[3].add(int(card[1]))
for i, ca in enumerate(c):
    for f in sorted(list(full - ca)):
        print(t[i] + ' ' + str(f))


Measured memory_bytes: 5608
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 char c;
 cin >> c;
 if(c == 'a' || c == 'e' || c == 'i' || c == 'u' || c == 'o'){
 cout << "vowel";
 }
 else{
 cout << "consonant";
 }
}

Measured memory_bytes: 256
import java.util.*

fun main(args: Array<String>) {
    val xx = Stack<Int>()

    Scanner(System.`in`).use {
        val n = it.nextInt()
        val x = it.nextInt()
        for (i in 0 until n) {
            val xxI = it.nextInt()
            if (xxI < x) {
                xx.push(x - xxI)
            } else {
                xx.push(xxI - x)
            }
        }
    }

    while (1 < xx.size) {
        val xxTmp = (0 until 2).map {
            xx.pop()
        }

        val i = if (xxTmp[1] < xxTmp[0]) {
            1
        } else {
            0
        }
        xx.push(xxTmp[i])
        val r = xxTmp[(i + 1) % 2] % xxTmp[i]

        if (0 < r) {
            xx.push(r)
        }
    }

    println(xx.pop())
}


Measured memory_bytes: 68344
#include<bits/stdc++.h>
#define Task "D"

using namespace std;
vector<int> adj[200005];
int n, q, ans[200005];

void dfs(int u, int dad){
    ans[u] += ans[dad];
    for(int v : adj[u])
        if (v != dad) dfs(v,u);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> q;
    int pos, val, u, v;
    for(int i = 1; i<n; ++i){
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i = 1; i<=q; ++i){
        cin >> pos >> val;
        ans[pos] += val;
    }
    dfs(1,0);
    for(int i = 1; i<=n; ++i) cout << ans[i] << " ";

    return 0;
}


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

int main() {
  int N;
  cin >> N;
  if(N == 1){
    cout << "Hello World" << endl;
  }
  else{
    int A,B;
    cin >> A;
    cin >> B;
    cout << A+B << endl;
  }
}


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

inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	for (; ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') f = -1;
	for (; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
	return x * f;
}

const int N = 4e6 + 5;;

bitset<N> f;

int main()
{
	int n = read(), sum = 0;
	f[0] = 1;
	
	for (int i = 1, x; i <= n; ++i)
	{
		sum += (x = read());
		f |= f << x;
	}
	
	for (int i = (sum + 1) / 2; i <= sum; ++i)
		if (f[i]) { printf("%d\n", i); break; }
	
	return 0;
}


Measured memory_bytes: 5096
row, column = map(int,input().split())
lis = [[0]*(column+1) for i in range(row+1)]
for i in range(row):

    inp = list(map(int,input().split()))
    lis[i] = inp + [0]

for i in range(row):
    for j in range(column):
        lis[row][j] += lis[i][j]
        lis[i][column] += lis[i][j]
        lis[row][column] += lis[i][j]

for i in range(row+1):
    print(*lis[i])


Measured memory_bytes: 6200
#include<bits/stdc++.h>
//#include<iostream>
//#include<cstdio>
//#include<cstring>
//#include<string>
//#include<queue>
//#include<cmath>
//#include<algorithm>
//#define debug1 cout<<"?"<<endl;
//#define debug2 cout<<"?"<<i<<endl;
#define PII pair<int,int>
typedef long long ll;
const int maxn=3e5+9;
const double pi=acos(-1);
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const double ep=1e-7;
using namespace std;
ll fac[maxn],inv[maxn];
ll pow_mod(ll a,ll n)
{
    ll ret =1;
    while(n)
    {
        if(n&1) ret=ret*a%mod;
          a=a*a%mod;
          n>>=1;
    }
    return ret;
}
void init()
{
    fac[0]=1;
    for(int i=1;i<maxn;i++)
    {
        fac[i]=fac[i-1]*i%mod;
    }
}
ll Cc(ll x, ll y)
{
    return fac[x]*pow_mod(fac[y]*fac[x-y]%mod,mod-2)%mod;
}
int main()
{
	init();
	ll n,k,ans=0,i;
	scanf("%lld%lld",&n,&k);
	for(i=0;i<=min(n-1,k);i++)ans=(ans+Cc(n,i)*Cc(n-1,i)%mod)%mod;
	printf("%lld\n",ans);
}

Measured memory_bytes: 2944
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;cin>>n;
  vector<int>a(n);
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  int count=0;
  for(int i=1;i<n-1;i++){
    if(a[i]<max({a[i-1],a[i],a[i+1]})&&a[i]>min({a[i-1],a[i],a[i+1]}))count++;
    else if((a[i]==a[i+1]&&a[i]>a[i-1])||(a[i-1]==a[i]&&a[i]>a[i+1]))count++;
  }
  cout<<count<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
 long n,R[200000]={0};
 
 scanf("%d",&n);
 for(int i=0;i<n;i++){
  scanf("%d",&R[i]);
 }

 long maxProfit=R[1]-R[0],mini=R[0];
 for(int i=1;i<n;i++){
  if(maxProfit<R[i]-mini){
   maxProfit=R[i]-mini;
  }
  if(mini>R[i]){
   mini=R[i];
  }
 }
 printf("%d\n",maxProfit);
 return 0;
}

Measured memory_bytes: 2596
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0;i < n;i++)
#define repr(i, n) for(int i = n;i >= 0;i--)
#define for(i, m, n) for(int i = m;i < n;i++)
#define forr(i, m, n) for(int i = m;i >= n;i--)
#define sort(v, n) sort(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define ll long long
#define ull unsigned long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

int main(){
    int a, b, c, d;
    cin >> a >> b >> c >> d;

    if((abs(a-b) <= d && abs(b-c) <= d) || abs(a-c) <= d) cout << "Yes" << endl;
    else cout << "No" << endl;
}


Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        final int N = sc.nextInt();
        final long K = sc.nextLong();
        int[] teleport = new int[N];
        for(int i=0; i<N; i++) {
            teleport[i]=sc.nextInt()-1;
        }

        boolean[] clear = new boolean[N];
        clear[0] = true;

        List<Integer> list = new ArrayList<>();     //<>の中のIntegerは冗長なのでいらないって言われます。実際めんどくさいので消してOK
        list.add(0);

        int twice = -1;     //初めて2回目に踏む町の番号(0<=twice<=N-1)

        for(int i=0; i<K; i++) {
            int x= teleport[list.get(i)];
            if(clear[x]) {      //既に踏んでいる町なら
                twice = x;      //twiceにxを代入しbreak
                break;
            }else {             //まだ踏んでない町なら
                list.add(x);    //行程をlistに記録して
                clear[x] = true;    //踏んだという印をつける
            }
        }

        /*
        ここまでで、もしループを踏む前に走査が終わった場合
        listの中身は{0, (0からテレポした先), (さらにテレポした先), ...}という風になって、
        そのsize()はK+1です。
        ただし、K回目にclear[x]==trueであった時、twiceを記録してbreakしてしまうので、
        twice==-1とは限りません。
         */

        if(twice==-1) {
            System.out.println(list.get((int)K)+1);     //ここが変更点。ループ到達前に走査が終わった場合は、「リストの最後の町」がそのまま答えになるはず。なおこの場合Kの大きさはたかだか2×10^5なのでテキトーにintにキャストしてよい。
        }else {
            int num =0;
            while(!list.isEmpty()) {      //小変更。好みの問題。
                if(list.get(0)==twice) {    //ループ開始点まで来たらそこで止める
                    break;
                }else {
                    list.remove(0);     //ループ開始点に到達するまで先頭の要素を消し続ける。最終的にループ構造だけが残る
                    num++;      //numでループの先頭までのステップ数を記録する
                }
            }

            /*
            K-num = ループの先頭に到達したあとさらに動かなければいけないステップ数
            list.size = ループ長
            なので、
             */

            System.out.println(list.get((int)((K-num)%list.size()))+1);     //これでOK。
        }
    }
}


Measured memory_bytes: 51220
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll v[100010];
ll berat[100010];
ll dp[110][100010];

ll ks(int a, int nilai){
	if(a == 0){
		if(nilai == 0) return 0;
		else return 3e12;
	}
	if(dp[a][nilai] != -1) return dp[a][nilai];
	
	dp[a][nilai] = ks(a - 1, nilai);
	if(v[a] <= nilai){
		dp[a][nilai] = min(dp[a][nilai], ks(a - 1, nilai - v[a]) + berat[a]);
	}
	return dp[a][nilai];
}

int main (){
	memset(dp,-1,sizeof dp);
	ll n,w;
	cin >> n >> w;
	for(int i = 1; i <= n; i++){
		cin >> berat[i] >> v[i];
	}
	ll ans = 0;
	for(int i = 0; i <= 100000; i++){
		ll res = ks(n,i);
		
		if(res <= w) ans = i;
	}
	
	cout << ans << endl;
}

Measured memory_bytes: 86272
// https://atcoder.jp/contests/abc087/tasks/abc087_b

#include <bits/stdc++.h>
#define REP(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define REPR(i, n) for (int(i) = (n); (i) >= 0; (i)--)
#define FOR(i, m, n) for (int(i) = (m); (i) < (n); i++)
#define INF 1e9
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;

int main()
{
  /* Magic word */
  // cin.tie(0);
  // ios::sync_with_stdio(false);
  /* ---------- */

  int a, b, c, x;
  int cnt = 0;

  cin >> a >> b >> c >> x;

  REP(i, a + 1)
  {
    REP(j, b + 1)
    {
      int total = i * 500 + j * 100;
      REP(k, c + 1)
      {
        if (total + k * 50 == x)
          cnt++;
      }
    }
  }

  cout << cnt << '\n';

  return 0;
}


Measured memory_bytes: 256
"use strict";

function Main(input) {
  let lines = input.split('\n');
  let M1 = lines[0].split(' ')[0] * 1;
  let M2 = lines[1].split(' ')[0] * 1;
  console.log((!(M1 === M2))*1);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


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

#define rep(i, a) for (int i = 0; i < (a); ++i)
#define REP(i, a, b) for (int i = (a); i < (b); ++i)
#define FORV(a, A) for (auto &a : A)

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

bool sosuu(int a) {
  int num = int(sqrt((double)a));
  REP(i, 2, num + 1) {
    if (a % i == 0) return false;
  }
  return true;
}

void Main() {
  int x;
  cin >> x;
  while (1) {
    if (sosuu(x)) {
      cout << x << endl;
      return;
    }
    x++;
  }
}

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

Measured memory_bytes: 256
n = int(input())

w = list(map(int, input().split()))

ba= abs(w[0] - sum(w[1:]))
for t in range(2,n):
    x1 = w[0:t]
    x2 = w[t:n]
    ab = abs(sum(x1)-sum(x2))
    if ab<ba:
        ba = ab
print(ba)

Measured memory_bytes: 3060
#include "bits/stdc++.h"
// Begin Header {{{
#define all(x) (x).begin(), (x).end()
#define rep(i, s, n) for (i64 i = (s), i##_limit = (n); i < i##_limit; ++i)
#define repr(i, s, t) for (i64 i = (s), i##_limit = (t); i >= i##_limit; --i)
#define repc(i, s, t) for (i64 i = (s), i##_limit = (t); i <= i##_limit; ++i)
#define var(type, ...) \
    type __VA_ARGS__;  \
    read(__VA_ARGS__);
#ifndef DBG
#define dump(...)
#endif
using namespace std;
using i64 = int_fast64_t;
using pii = pair<i64, i64>;
template <class T, class U>
inline bool chmax(T &a, const U &b) {
    return b > a && (a = b, true);
}
template <class T, class U>
inline bool chmin(T &a, const U &b) {
    return b < a && (a = b, true);
}
constexpr int INF = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;

template <class T>
inline vector<T> makeV(const T &initValue, size_t sz) {
    return vector<T>(sz, initValue);
}

template <class T, class... Args>
inline auto makeV(const T &initValue, size_t sz, Args... args) {
    return vector<decltype(makeV<T>(initValue, args...))>(
        sz, makeV<T>(initValue, args...));
}

template <class T>
inline istream &operator>>(istream &is, vector<T> &vec) {
    for (auto &e : vec) is >> e;
    return is;
}

inline void read() {}

template <class Head, class... Tail>
inline void read(Head &head, Tail &... tail) {
    cin >> head;
    read(tail...);
}

inline void print() { cout << "\n"; }

template <class Head, class... Tail>
inline void print(Head &&head, Tail &&... tail) {
    cout << head;
    if (sizeof...(tail)) cout << ' ';
    print(forward<Tail>(tail)...);
}

template <class T>
inline ostream &operator<<(ostream &os, const vector<T> &vec) {
    static constexpr const char *delim[] = {" ", ""};
    for (const auto &e : vec) os << e << delim[&e == &vec.back()];
    return os;
}

template <class Container>
struct Rev {
    Container &x_;
    inline Rev(Container &x) : x_(x) {}
    inline auto begin() { return rbegin(x_); }
    inline auto end() { return rend(x_); }
};
// }}} End Header

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.setf(ios_base::fixed);
    cout.precision(12);

    var(int, N, D);
    const int K = 2 * D + 1;
    print((N + K - 1) / K);

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define db(a) cout << fixed << #a << " = " << a << endl;

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const ll MOD = 1e9 + 7;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	ll n;
	cin >> n;
	vector<ll> A(n);
	ll s = 0;
	for (int i = 0; i < n; i++) {
		cin >> A[i];
		s += A[i];
		s %= MOD;
	}
	ll ans = (s * s) % MOD;
	for (int i = 0; i < n; i++) {
		ans -= A[i] * A[i];
		ans %= MOD;
		if (ans < 0) ans += MOD;
	}
	if (ans % 2 == 0) {
		cout << ans / 2 << endl;
	} else {
		ans *= 500000004LL;
		ans %= MOD;
		cout << ans << endl;
	}
}

//(a + b + c)**2  - a**2 - b**2 - c**2 / 2


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

int main() {
	int w,h,x,y,r;
	cin>>w>>h>>x>>y>>r;
	if(x>0&&y>0&&x-r>=0&&y-r>=0&&x<w&&x+r<=w&&y<h&&y+r<=h)
		cout<<"Yes"<<endl;
	else
		cout<<"No"<<endl;
	return 0;
}


Measured memory_bytes: 3120
#include <bits/stdc++.h>
#define REP(i, n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i, a, b) for(ll i = (a); i < (ll)b; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF (1ll << 60)
#define sz(x) int(x.size())
using namespace std;
typedef long long ll;
using vl = vector<ll>;
using vvl = vector<vl>;
typedef double db;
typedef string str;
typedef pair<ll, ll> p;
constexpr int MOD = 1000000007;
using ll = long long;
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(const std::vector<int> &v) {
    std::for_each(v.begin(), v.end(), [](int x) { std::cout << x << " "; });
    std::cout << std::endl;
}
ll dp[51][51][3010];
// dp[i][j][k]
// i枚目までのカードでj枚えらんで合計がkである組み合わせ
//遷移の仕方は
// dp[i+1][j][k] = dp[i][j][k]
// dp[i+1][j+1][k+x[i]] = dp[i][j][k]
int main() {
    int N, A;
    cin >> N >> A;
    vector<int> x(N);
    int avg_cnt = 0;
    REP(i, N) { cin >> x[i]; }
    dp[0][0][0] = 1;
    REP(i, N) {
        REP(j, N) {
            REP(k, 2500) {
                dp[i + 1][j][k] += dp[i][j][k];
                dp[i + 1][j + 1][k + x[i]] += dp[i][j][k];
            }
        }
    }
    ll ans = 0LL;
    for(int i = 1; i <= N; i++) {
        ans += dp[N][i][i * A];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 60160
#[allow(unused_macros)]
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)*}
    };
}

#[allow(unused_macros)]
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)*}
    };

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

#[allow(unused_macros)]
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, bytes) => {
        read_value!($next, String).into_bytes()
    };

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

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

#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::{BinaryHeap, HashMap};

#[allow(dead_code)]
type Graph = Vec<Vec<usize>>;

fn main() {
    input! {
        n: usize,
        a: [[i64; n]; n],
    }

    let mut cost = vec![0; 1 << n];

    for i in 0..(1 << n) {
        for j in 0..n {
            for k in 0..j {
                if (i >> j) & 1 > 0 && (i >> k) & 1 > 0 {
                    cost[i] += a[j][k];
                }
            }
        }
    }

    let mut dp = vec![0; 1 << n];

    for mask in 0..(1 << n) {
        let mut group = mask;
        while group > 0 {
            dp[mask] = max(dp[mask], dp[mask ^ group] + cost[group]);
            group = (group - 1) & mask;
        }
    }

    println!("{}", dp[(1 << n) - 1]);
}


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

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	const int N = 55;
	vector<vector<long long>> C(N, vector<long long>(N, 0));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j <= i; j++) {
			if (i == j || j == 0) C[i][j] = 1;
			else C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
		}
	}
	int n, k, S, T; cin >> n >> k >> S >> T;
	vector<int> a;
	for (int i = 0; i < n; i++) {
		int b; cin >> b;
		if ((b & S) != S) continue;
		if ((b | T) != T) continue;
		a.push_back(b);
	}
	n = a.size();
	vector<int> bts;
	bool flag = true;
	for (int i = 0; i < 18; i++) {
		if ((S >> i & 1) && (~T >> i & 1)) flag = false;
		if ((~S >> i & 1) && (T >> i & 1)) {
			bts.push_back(i);
		}
	}
	int m = bts.size();
	vector<long long> nums(m, 0);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (a[i] >> bts[j] & 1) nums[j] |= 1ll << i;
		}
	}
	long long ans = 0;
	if (flag) {
		long long tot = 0;
		vector<int> add(n + 1, 0), del(n + 1, 0);
		vector<vector<long long>> st(1 << m);
		st[0].push_back((1ll << n) - 1);
		for (int i = 1; i < (1 << m); i++) {
			int bc = __builtin_popcount(i);
			for (int j = 0; j < m; j++) {
				if (i >> j & 1) {
					for (auto val : st[i ^ (1 << j)]) {
						if (val & nums[j]) st[i].push_back(val & nums[j]);
						if (val & (~nums[j])) st[i].push_back(val & (~nums[j]));
					}
					break;
				}
			}
			long long sgn = 1;
			if (bc & 1) sgn = -1;
			for (auto val : st[i]) {
				bc = __builtin_popcountll(val);
				if (sgn > 0) add[bc]++;
				else del[bc]++;
//				tot += sgn * C[bc][c];
			}
		}
		for (int c = 1; c <= min(n, k); c++) {
			tot += C[n][c];
			for (int i = 0; i <= n; i++) {
				tot += C[i][c] * (add[i] - del[i]);
			}
		}
		ans += tot;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 139580
n=int(input())
a=0
b=0
c=0
d=0
for _ in range(n):
  s=input()
  if s=='AC':
    a+=1
  elif s=='WA':
    b+=1
  elif s=='TLE':
    c+=1
  else:
    d+=1
print('AC x ',end='')
print(a)
print('WA x ',end='')
print(b)
print('TLE x ',end='')
print(c)
print('RE x ',end='')
print(d)


Measured memory_bytes: 69832
N = int(input())
e = [0] * (N + 1)
MOD = 10 ** 9 + 7
for i in range(1, N + 1):
    K = i
    for j in range(2, i + 1):
        while K % j == 0:
            e[j] += 1
            K //= j

ans = 1
for i in range(1, N + 1):
    if e[i] > 0:
        ans *= e[i] + 1
        ans %= MOD

print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//23:02
ll a[20];
int main() {
    int n,k;
    cin >> n >> k;
    ll ans = 1e18;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < (1 << n); i++) {
        int cnt = 0;
        for (int j = 0; j < n; j++) {
            if ((i >> j) & 1) cnt++;
        }
        if (cnt >= k) {
            ll h = 0;
            ll sum = 0;
            for (int j = 0; j < n; j++) {
                if ((i >> j) & 1) {
                    if (a[j] <= h) {
                        sum += h + 1 - a[j];
                        h++;
                    } else {
                        h = a[j];
                    }
                } else {
                    if (a[j] > h) h = a[j];
                }
            }
            ans = min(ans, sum);
        }
    }
    cout << ans << endl;
    return 0;
}

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

int main(){

    int a ,n;
    int sum = 0;
    int s1 = 0;
    int s2 ,t;

    std::cin >> n;

    std::vector<int> v(n);
    std::vector<int> s(n);

    for(a = 0; a < n; a++){
        std::cin >> v[a];
        sum += v[a];
    }

    
    for(a = 0;a < n; a++){
        s1 += v[a];
        s2 = sum - s1;

        t = s1 - s2;

        if(t < 0){
            t *= -1;
        }

        s[a] = t;

    }

    std::sort(s.begin() ,s.end());

    std::cout << s[0] << std::endl;

    return 0;   
}


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

int main(){
  string T_taro, T_hanako;
  int n, p_taro=0, p_hanako=0;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>T_taro>>T_hanako;
    if(T_taro > T_hanako) p_taro += 3;
    else if(T_taro == T_hanako){
      p_taro++;
      p_hanako++;
    }
    else p_hanako += 3;
  }
  cout<<p_taro<<" "<<p_hanako<<endl;
  return 0;
}



Measured memory_bytes: 3204
use std::io::*;

fn contains(v: &Vec<i32>, num: i32)-> bool {
    v.iter().any(|&i| i==num)
}

fn main() {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    let nums: Vec<i32> = buf.split_whitespace().map(|n| n.parse().unwrap()).collect::<Vec<i32>>();

    let x = nums[0];
    let n = nums[1];

    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    let mut nums: Vec<i32> = buf.split_whitespace().map(|n| n.parse().unwrap()).collect::<Vec<i32>>();

    nums.sort_by(|x, y| x.cmp(y).reverse());

    if nums.len() == 0 {
        let out = stdout();
        let mut out = out.lock();
        writeln!(out, "{}\n", x).unwrap();
        return;
    }

    let mut p = x;
    let mut less = 0;
    loop {
        if !contains(&nums, p) {
            less = p;
            break;
        }
        p -= 1;
    }

    let mut p = x;
    let mut more = 0;
    loop {
        if !contains(&nums, p) {
            more = p;
            break;
        }
        p += 1;
    }

    if x - less <=  -(x - more) {
        let out = stdout();
        let mut out = out.lock();
        writeln!(out, "{}\n", less).unwrap();
    } else {
        let out = stdout();
        let mut out = out.lock();
        writeln!(out, "{}\n", more).unwrap();
    }
}


Measured memory_bytes: 2192
{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE LambdaCase #-}

module Main where

import qualified Data.ByteString.Char8 as B8
import Data.Maybe (fromJust)
import Data.Char (toUpper)
import Data.List
import qualified Data.Map as M
import Data.Ix (range)
import Control.Monad
import Control.Applicative
import Text.Printf

readDigits = map read <$> words <$> getLine :: IO [Int]

solve :: Integer -> Integer -> String
solve a b
    | a > b = "GREATER"
    | a < b = "LESS"
    | a == b = "EQUAL"

main :: IO ()
main = do
    a <- readLn 
    b <- readLn 
    putStrLn $ solve a b

Measured memory_bytes: 636
n,m=map(int,input().split())
p=10**9+7
w=[]
M=m
i=2
cnt=0

def f(n,k,p):
    if k==0:
        return 1
    elif k%2==0:
        return (f(n,k//2,p)**2)%p
    else:
        return (n*f(n,k-1,p))%p

while i*i<=M:
    if m%i==0:
        cnt+=1
        m=m//i
    else:
        if cnt>=1:
            w.append(cnt)
        cnt=0
        i+=1
if m>1:
    w.append(1)

ans=1
for x in w:
    a=1
    for i in range(x):
        a=(a*(n+i))%p
    b=1
    for i in range(x):
        b=(b*(i+1))%p

    ans=(ans*a*f(b,p-2,p))%p
print(ans%p)



Measured memory_bytes: 63448
#include "bits/stdc++.h"
using namespace std;

int main() {
	
	int k, s;
	cin >> k >> s;
	int a = 0;
	for (int i=0; i<=k; i++) {
		for (int j=0; j<=k; j++) {
			int sm = i + j;
			int o = s - sm;
			if (o >= 0 && o <= k) a++;
		}
	}
	cout << a << endl;
	
}


Measured memory_bytes: 256
// IOI 2021
#include <bits/stdc++.h>
using namespace std;
 
#define endl '\n'
#define ends ' '
#define die(x) return cout << x << endl, 0
#define all(v) v.begin(), v.end()
#define sz(x) (int)(x.size())
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << ends << H; debug_out(T...); }
#define debug(...) cerr << "{" << #__VA_ARGS__ << "}:", debug_out(__VA_ARGS__)
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9;
const ll MOD = 924844033;
 
////////////////////////////////////////////////////////////////////
 
const int N = 2e3 + 5;

int F[N], DP[N][N], M[N];

int main() {
 
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	mt19937 Rnd(time(0));
			
 	F[0] = 1;
	for (int i = 1; i < N; i++) F[i] = 1LL * i * F[i - 1] % MOD;
	DP[0][0] = 1;
	for (int i = 1; i < N; i++) {
		DP[i][0] = 1;
		for (int j = 1; j <= i / 2; j++) DP[i][j] = (DP[i - 1][j] + DP[i - 2][j - 1]) % MOD;
	}
	int n, k; cin >> n >> k;
	M[0] = 1;
	for (int i = 0; i < min(n, 2 * k); i++) {
		int p = (n - 1 - i) / k + 1;
		if (i >= k) p++;
		for (int j = N - 1; j >= 0; j--) for (int l = 1; l <= j && l <= p / 2; l++) 
		    M[j] = (M[j] + 1LL * M[j - l] * DP[p][l] % MOD) % MOD;
	}
	int ans = 0;
	for (int i = 0; i <= n; i++) {
		int z = (i & 1) ? -1 : +1;
		ans = (ans + 1LL * z * M[i] * F[n - i] % MOD + MOD) % MOD;
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 15576
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_map>
#include<climits>
#include<cstdlib>
#include<cmath>
#include<string>
#include<iomanip>
#include<bitset>

using namespace std;

#define ll long long int

ll const MOD = 1000000007;
ll const INF = (long long int)1 << 61;

ll mypow(ll x,ll n){
    ll ret = 1;
    while(n > 0){
        if(n&1){
            ret = (ret*x)%MOD;
        }
        x = (x*x)%MOD;
        n >>= 1;
    }
    return ret;
}

struct mypair{
    string a;
    int b;
    int idx;

    bool operator <(const mypair &right)const{
        if(a == right.a){
            return b > right.b;
        }else{
            return a < right.a;
        }
    }
};

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

    vector<mypair> q;
    for(int i = 0; i < n; i++){
        string a;
        int b;
        cin >> a >> b;
        q.push_back(mypair{a,b,i+1});
    }

    sort(q.begin(),q.end());

    for(int i = 0; i < n; i++){
        cout << q[i].idx << endl;
    }

    return 0;
}

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

int main() {
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	int n;
	cin>>n;
	int num[n+1];
	for(int i=1;i<=n;i++)
		scanf("%d",&num[i]);
	
	int put[n+1],ans=0;
	for(int i=n/2 +1;i<=n;i++) {
		put[i]=num[i];
		if(put[i]==1) ans++;
	}
	
	for(int i=n/2;i>0;i--) {
		int now=2*i,get=0;
		while(now<=n) {
			get+=put[now];
			now+=i;
		}
		get%=2;
		
		if(get!=num[i]) {
			put[i]=1;
			ans++;
		}
		else put[i]=0;
	}
	
	cout<<ans<<endl;
	for(int i=1;i<=n;i++)
		if(put[i]==1) cout<<i<<" ";
	cout<<endl;
	
	return 0;
}
/*
1 0 1 0 1 0 0 1 1 1 0 0 1 1 1 0 1 
1 2 3 4 5 6 7 8 9 1011121314151617
*/


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

long long wt[105],value[105],dp[105][100005];   ///dp[i][j] means minimum weight for making profit exactly j by considering item i to n

int main()
{
    long long i,j,k,n,cap,ans;
    cin>>n>>cap;
    for(i=1 ; i<=n ; i++)   cin>>wt[i]>>value[i];

    dp[n+1][0] = 0;
    for(i=1 ; i<=1e5 ; i++) dp[n+1][i] = 1e18;

    for(i=n ; i>=1 ; i--){
        for(j=0 ; j<=1e5 ; j++){
            if(value[i] > j)
                dp[i][j] = dp[i+1][j];
            else
                dp[i][j] = min(dp[i+1][j] , wt[i]+dp[i+1][j-value[i]]);
        }
    }

    for(i=1e5 ; i>=0 ; i--){
        if(dp[1][i] <= cap){
            cout<<i<<endl;
            break;
        }
    }

    return 0;
}


Measured memory_bytes: 82536
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll INF = 1ll<<30;
const ll longINF = 1ll<<60;
const ll MOD = 1000000007;
const double EPS = 1e-9;
const bool debug = 0;
//---------------------------------//

int N;
string S;
int dp[5000][5000];

int dfs(int s, int t) {
	int &res = dp[s][t];
	if (~res) return res;
	res = 0;
	
	if (s < N && t < N && S[s] == S[t]) res = dfs(s + 1, t + 1) + 1;
	
	return res;
}

int main() {
	cin >> N >> S;
	
	int ans = 0;
	
	memset(dp, -1, sizeof(dp));
	REP(i, N) FOR(j, i + 1, N) {
		chmax(ans, min(dfs(i, j), j - i));
	}
	
	cout << ans << endl;
	return 0;
}

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

const ll MOD = 998244353;

ll mod(ll n, ll m) {
  ll res = n % m;
  if (res < 0) res += m;
  return res;
}

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


int main(void){
  ll N;
  cin >> N;
  vector<ll> a(N);
  for (int i = 0; i < N; i++) {
    cin >> a.at(i);
  }
  ll S = accumulate(a.begin(), a.end(), 0);
  
  vector<vector<ll>> dp1(N+1, vector<ll>(S+1, 0));
  vector<vector<ll>> dp2(N+1, vector<ll>(S+1, 0));
  dp1.at(0).at(0) = 1;
  dp2.at(0).at(0) = 1;
  
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < S; j++) {
      dp1.at(i+1).at(j) += dp1.at(i).at(j) * 2 % MOD;
      dp2.at(i+1).at(j) += dp2.at(i).at(j) % MOD;
    }
    for (int j = a.at(i); j < S+1; j++) {
      dp1.at(i+1).at(j) += dp1.at(i).at(j-a.at(i)) % MOD;
      dp2.at(i+1).at(j) += dp2.at(i).at(j-a.at(i)) % MOD;
    }
  }
  
  ll pat;
  pat = modpow(3, N, MOD);
  ll s1 = 0;
  ll s2 = 0;

  if (S % 2 == 0) {
    for (int i = S/2; i < S+1; i++) {
      s1 += 3 * dp1.at(N).at(i);
      s1 %= MOD;
    }
    s2 = 3 * dp2.at(N).at(S / 2);
  } else {
    for (int i = S/2+1; i < S+1; i++) {
      s1 += 3 * dp1.at(N).at(i);
      s1 %= MOD;
    }
  }
  cout << mod(pat - s1 + s2, MOD) << endl;
}


Measured memory_bytes: 423744
n = int(input())
A = list(map(int, input().split()))

p = 1000
s = 0

for i, j in zip(A, A[1:]):
  if i < j:
    d, m = divmod(p, i)
    s += d
    p = m
  elif i > j:
    p += s * i
    s = 0

if s != 0:
  p += s * A[-1]

print(p)

Measured memory_bytes: 9176
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#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 rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define repc2(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define inf 2e9
#define linf 9000000000000000000ll
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

double a, b, h, m;

int main() {
    cin >> a >> b >> h >> m;
    double sx, sy, lx, ly;
    sx = a * cos(M_PI_2 - h * (M_PI / 6.) + -m * (M_PI / 30. / 12.));
    sy = a * sin(M_PI_2 - h * (M_PI / 6.) + -m * (M_PI / 30. / 12.));
    lx = b * cos(M_PI_2 - m * (M_PI / 30.));
    ly = b * sin(M_PI_2 - m * (M_PI / 30.));
    cout << fixed << setprecision(12);
    cout << sqrt((sx - lx) * (sx - lx) + (sy - ly) * (sy - ly)) << endl;
    return 0;
}

Measured memory_bytes: 4088
#include <bits/stdc++.h>
using namespace std;
#define SELECTER(_1, _2, _3, SELECT, ...) SELECT
#define REP1(i, n) for(int i=0; i<n; i++)
#define REP2(i, a, b) for(int i=a; i<b; i++)
#define REP(...) SELECTER(__VA_ARGS__, REP2, REP1,) (__VA_ARGS__)
#define MOD 1'000'000'007

template <class T> ostream& operator<<(ostream& os, const vector<T>& v){ os << "{"; for(size_t i=0; i<v.size(); i++) os << v[i] << (i+1==v.size() ? "" : ", "); os << "}"; return os; }
template <class T, class U> ostream& operator<<(ostream& os, const pair<T, U>& p){ return os << "{" << p.first << ", " << p.second << "}"; }


int main(){
    long long N, M, L, Q;
    cin >> N >> M >> L;
    vector<vector<long long>> D(N, vector<long long>(N, 1LL<<50));
    REP(i, M){
        int A, B, C;
        cin >> A >> B >> C;
        A--; B--;
        D[A][B] = D[B][A] = C;
    }
    cin >> Q;
    vector<pair<int, int>> st(Q);
    REP(i, Q){
        int s, t;
        cin >> s >> t;
        s--; t--;
        st[i] = make_pair(s, t);
    }


    REP(k, N) REP(i, N) REP(j, N)
        D[i][j] = min(D[i][j], D[i][k]+D[j][k]);

    REP(i, N) REP(j, N)
        D[i][j] = (D[i][j]<=L ? 1: 1LL<<50);

    REP(k, N) REP(i, N) REP(j, N)
        D[i][j] = min(D[i][j], D[i][k]+D[j][k]);

    REP(i, Q){
        int s = st[i].first;
        int t = st[i].second;
        if(D[s][t] >= (1LL<<50)) cout << -1 << endl;
        else cout << D[s][t]-1 << endl;
    }
    return 0;
}


Measured memory_bytes: 2048
#include <cstdio>
#include <iostream>
#include <map>
using namespace std;
typedef long long ll;

ll N, X, M;
ll A[100005];
map<ll, int> reverse_map;

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

int main() {
  cin >> N >> X >> M;

  A[1] = X;
  reverse_map[X] = 1;
  int loop_start = 1, loop_end = N+1;
  for (int i = 1; i < N; i++) {
    ll n = modpow(A[i], 2, M) % M;
    A[i+1] = n;
    // printf("A[%d] = %lld, ", i+1, n); if (i % 10 == 0) puts("");
    if (reverse_map[n] > 0) {
      loop_start = reverse_map[n];
      loop_end = i;
      break;
    }
    reverse_map[n] = i+1;
  }

  ll mod = (N - loop_start + 1) % (loop_end - loop_start + 1);
  ll times = (N - loop_start + 1) / (loop_end - loop_start + 1);

  ll loop_sum = 0;
  for (int i = loop_start; i <= loop_end; i++) { loop_sum += A[i]; }

  ll ans = 0;
  for (int i = 1; i < loop_start; i++) { ans += A[i]; }
  ans += times * loop_sum;

  for (int i = 0; i < mod; i++) { ans += A[loop_start+i]; }

  // printf("loop_start = %d, loop_end = %d, loop_sum = %lld, times = %lld, mod = %lld\n", loop_start, loop_end, loop_sum, times, mod);

  printf("%lld\n", ans);
}


Measured memory_bytes: 7132
#define _USE_MATH_DEFINES
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<math.h>
#include<map>
#include<iomanip>
#include<functional>
#include<limits>
#include <unordered_map>
#include <numeric>
#include <array>
#include <queue>
#include <chrono>
#include <random>
#include <fstream>


using namespace std;
using  ull = unsigned long long int;

#define rep(i,n,m) for(long long int i=n;i<(long long int)(m);i++)
#define INF (1<<29)
#define MD 1000000007

int main() {

	int n;
	cin >> n;
	int alice, bob;
	alice = bob = 0;
	vector<int>card(n);

	rep(i, 0, n)cin >> card[i];


	rep(i, 0, n) {
		std::vector<int>::iterator maxIt = std::max_element(card.begin(), card.end());
		size_t maxIndex = std::distance(card.begin(), maxIt);
		if (i % 2 == 0)alice += card[maxIndex];
		else bob += card[maxIndex];
		card[maxIndex] = 0;
	}

	cout << alice - bob << endl;

	return 0;
}

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

using namespace std;

int main(void)
{
  int N, M;

  cin >> N >> M;

  vector<vector<int>> table(N, vector<int>(6000, 0));
  
  multiset<pair<int,int>> ABlist;
  
  for(int i=0;i<N;i++){
    int a,b;
    cin>>a>>b;
    ABlist.insert(make_pair(a,b));
  }
  
  
  int tmax = 0;
  auto itr = ABlist.begin();

  for (int i = 0; i < N; i++)
  {
    pair<int,int> p = *itr;
    int a = p.first;
    int b = p.second;
    itr++;

    for (int j = 0; j < 6000; j++)
    {

      if (i == 0)
      {
        tmax = b;
        if (j < a)
        {
          table[i][j] = 0;
        }
        else
        {
          table[i][j] = b;
        }

        continue;
      }
      
      if(j<a){
        table[i][j] = table[i - 1][j];
      }
      else if (j < M)
      {
        table[i][j] = max(table[i - 1][j], table[i - 1][j - a] + b);
      }
      else if(j < M+a){
        table[i][j] = max(table[i - 1][j], table[i - 1][j - a] + b);
      }
      else
      {
        table[i][j] = tmax;
      }

      if (tmax < table[i][j])
      {
        tmax = table[i][j];
      }
    }
  }

  cout << tmax << endl;

  return 0;
}

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

using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;

#define INF LONG_MAX
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.end(),a.begin()
#define endl "\n"

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

  int N;
  string S;
  cin>>N>>S;
  ll res=0;
  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
      if(i+j<N&&i-j>=0&&S[i-j]!=S[i+j]&&S[i]!=S[i-j]&&S[i]!=S[i+j])res++;
    }
  }
  ll ans=0;
  vector<int>lR(N),rR(N);
  vector<int>lG(N),rG(N);
  vector<int>lB(N),rB(N);
  for(int i=1;i<N;i++){
    lR[i]=lR[i-1];
    lG[i]=lG[i-1];
    lB[i]=lB[i-1];
    if(S[i-1]=='R')lR[i]++;
    if(S[i-1]=='G')lG[i]++;
    if(S[i-1]=='B')lB[i]++;
  }
  for(int i=N-2;i>=0;i--){
    rR[i]=rR[i+1];
    rG[i]=rG[i+1];
    rB[i]=rB[i+1];
    if(S[i+1]=='R')rR[i]++;
    if(S[i+1]=='G')rG[i]++;
    if(S[i+1]=='B')rB[i]++;
  }
  for(int i=1;i<N-1;i++){
    if(S[i]=='R')ans+=lG[i]*rB[i]+lB[i]*rG[i];
    if(S[i]=='G')ans+=lR[i]*rB[i]+lB[i]*rR[i];
    if(S[i]=='B')ans+=lR[i]*rG[i]+lG[i]*rR[i];
  }
  cout<<ans-res<<endl;
  return 0;
}


Measured memory_bytes: 3732