akhauriyash/Code-Regression huggingface dataset:
// 2018/01/15 Tazoe

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
	while(true){
		int x, y, s;
		cin >> x >> y >> s;

		if(x==0 && y==0 && s==0)
			break;

		int tmax = -1;			// 変更後の最大価格

		for(int a=1; a<=s-1; a++){		// 1つ目の税抜価格
			int ax = a*(100+x)/100;
			int ay = a*(100+y)/100;

			for(int b=1; b<=s-1; b++){		// 2つ目の税抜価格
				int bx = b*(100+x)/100;
				int by = b*(100+y)/100;

				if(ax+bx==s){				// 合計がsだったら
					tmax = max(tmax, ay+by);
				}
				else if(ax+bx>s){			// sを超えたら
					break;
				}
			}
		}

		cout << tmax << endl;
	}

	return 0;
}



Measured memory_bytes: 3092
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=5005;
int n,k;
string s;
int main()
{
	cin>>n>>k;
	cin>>s;
	char c='z'+1;
	int L=0,R=0;
	string tmp;
	for(int i=0;i<=n;i++)
		tmp+='z';
	for(int i=0,j=0;i<n;i=j)
	{
		j=i;
		while(j<n&&s[i]==s[j]) j++;
		if(s[i]<c) c=s[i],L=i,R=j-1,tmp=s.substr(j);
		else if(s[i]==c&&j-i>R-L+1) L=i,R=j-1,tmp=s.substr(j);
		else if(s[i]==c&&j-i==R-L+1&&s.substr(j)<tmp) L=i,R=j-1,tmp=s.substr(j);
	}
	if(k==1)
	{
		if(s[n-1]!=c)
		{
			string t=s;
			reverse(t.begin(),t.end());
			s+=t;
			s=s.substr(L,n);
			cout<<s; 
		}
		else
		{
			int cnt=0,now=n-1;
			while(now>=0&&s[now]==c) now--,cnt++;
			string t=s;
			reverse(t.begin(),t.end());
			string st=s+t;
			st=st.substr(now+1,n);
			t=s;
			reverse(t.begin(),t.end());
			s+=t;
			s=s.substr(L,n);
			cout<<min(st,s);
		}
		return 0;
	}
	if(R!=n-1)
	{
		int cnt=0,now=n-1;
		while(now>=0&&s[now]==c) now--,cnt++;
		string t=s.substr(0,now+1);
		reverse(t.begin(),t.end());
		if(cnt*2<R-L+1||(cnt*2==R-L+1&&tmp<t))
		{
			string t=s;
			reverse(t.begin(),t.end());
			s+=t;
			int r=(n-1-L)+n,l=r-n+1;
			s=s.substr(l,n);
			k--;
		}
	}
	int pre=n-1;
	while(pre>=0&&s[pre]==c) pre--;
	pre++;
	for(int i=1;i<k;i++)
	{
		string t=s;
		reverse(t.begin(),t.end());
		s+=t;
		int r=(n-1-pre)+n,l=r-n+1;
		s=s.substr(l,n);
		pre=n-1;
		while(pre>=0&&s[pre]==c) pre--;
		pre++;
		if(pre==0) break;
	}
	string t=s;
	reverse(t.begin(),t.end());
	s+=t;
	int l=pre,r=l+n-1;
	s=s.substr(l,n);
	cout<<s;
	return 0;
}

Measured memory_bytes: 3696
#include <stdio.h>

int main(void)
{
    int a,b;
    int c;
    int count;
    
    while (scanf("%d %d", &a, &b) != EOF){
                
        c = (a + b);
        count = 0;
        while (c != 0){
            c = c / 10;
            count++;
        }
        
        printf("%d\n", count);
        

    }
    return (0);
}


Measured memory_bytes: 2032
n,k= map(int, input().split())

if k==0:
    print(pow(n,2))
    exit()

ans=0
# あまりの数で場合わけ
for i in range(k,n+1):
    ans+=n-i
    for j in range(1,int(pow(n-i,0.5))+1):
        ans+=max((n-i)//j-i,0)
        if j>i:
            ans+=max((n-i)//j-int(pow(n-i,0.5)),0)


print(ans)

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

int main() {
  int N, sum = 0;
  cin >> N;
  vector<int> L(2 * N);
  for(int i = 0; i < 2 * N; i++){
    cin >> L.at(i);
  }
  sort(L.begin(), L.end());
  for(int i = 0; i < N; i++){
    sum += L.at(2 * i);
  }
  cout << sum << endl;
}

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

using namespace std;

#define relu(x) max(x, 0l)

int main() {
    int n, k;
    cin >> n >> k;
    long a[n], rui[n+1], top[n+1];
    for (auto &ai:a) cin >> ai;
    rui[0] = top[0] = 0;
    for (int i=0; i<n; i++) {
        rui[i+1] = rui[i] + a[i];
        top[i+1] = top[i] + relu(a[i]);
    }
    long ans = 0;
    for (int i=0; i<=n-k; i++)
        ans = max(ans, top[n] - top[i+k] + relu(rui[i+k] - rui[i]) + top[i]);
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define ll long long int
#define ld long long double
#define veci vector<ll>
#define it map<string, ll>::iterator
#define itr map<char, ll>::iterator
#define MOD 1000000007
#define test int T;cin>>T;while(T--)
#define nl "\n"
#define FULL(iii) iii.begin(),iii.end()
#define setbit(_) __builtin_popcount(_)
#define MAX 9223372036854775807 
#define TOUPR(str) trsform(str.begin(), str.end(),str.begin(), ::toupper)
#define TOLWR(str) trsform(str.begin(), str.end(),str.begin(), ::tolower)
#define pb push_back
#define len(s) s.length()
//#define cout cout<<setprecision(15)
#define N "NO"
#define Y "YES"
#define maxe(arr) *max_element(FULL(arr))
#define PI 3.141592653589793

int main()
{
    fio;
    ll n,i,s=0;
    cin>>n;
    veci a(n+1),dp(n+1);
    a[0]=1e7;
    for(i=1;i<=n;i++)
    cin>>a[i];
    dp[0]=0;
    dp[1]=0;
    for(i=2;i<=n;i++)
    {
        dp[i]=min(dp[i-1]+abs(a[i-1]-a[i]),dp[i-2]+abs(a[i-2]-a[i]));
    }
    cout<<dp[n]<<nl;
}

Measured memory_bytes: 1792
from itertools import product
n,w=map(int, input().split())
a=[list(map(int, input().split())) for i in range(n)]
ans=0

c=list(product([1,-1],repeat=3))
for i,j,k in c:
    a.sort(key= lambda x: i*x[0] +j*x[1] +k*x[2],reverse=True)
    a2=[i*s[0]+j*s[1]+k*s[2] for s in a]
    ans=max(ans,sum(a2[:w]))
print(ans)

Measured memory_bytes: 3432
n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

ans = 0
ans += B[A[0]-1]
for i in range(1,len(A)):
  ans += B[A[i]-1]
  if A[i] == A[i-1]+1:
    ans += C[A[i-1]-1]
    
print(ans)


Measured memory_bytes: 3064
def main():
    def gcd(a,b):
        while b!=0:
            a,b=b,a%b
        return a
    def lcm(a, b):
        return (a * b)//gcd(a,b)
    def ans(N,C,D):
        return N-N//C-N//D+N//lcm(C,D)

    A,B,C,D = map(int,input().split())
    print(ans(B,C,D)-ans(A-1,C,D))
    
if __name__=="__main__":
    main()

Measured memory_bytes: 3064
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<string>

using namespace std;

int main(void)
{
	int N,K;

	int A[100010];

	int Nadd = 100010;

	int add;

	cin >> N >> K;

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

		if (Nadd>A[i]) 
		{
			Nadd = A[i];

			add = i;
		}
	}

	sort(A, A + N);

	int k = 0;

	while (N > 0) 
	{
		if (k==0) 
		{
			N -= K;
		}
		else
		{
			N -= (K - 1);
		}

		k++;
	}

	cout << k << endl;

	
	
	
	
	return 0;
}



Measured memory_bytes: 640
using System;
using System.Collections.Generic;
using System.Data;
using System.Diagnostics;
using System.Globalization;

namespace Csharponly
{
    class Program
    {
        static public void Main()
        {

            string input = onestring();
            int howlong = input.Length;
            string ans = "No";
            for(int i = 0; i < howlong; i++)
            {
                if(input.Substring(i,1) == "7")
                {
                    ans = "Yes";
                    break;
                }
            }


            Console.WriteLine(ans);

        }
    



        //一つの文字列を受け渡す
        static string onestring()
        {
            return Console.ReadLine();
        }

        //複数の文字列を配列で受け渡す
        //文字列と文字列の間は" "で区切る
        static string[] arraystring()
        {
            return Console.ReadLine().Split(' ');
        }

        //一つの数字を受け渡す
        static int oneint()
        {
            return int.Parse(Console.ReadLine());
        }

        //複数の数字を配列で受け渡す
        //数字と数字の間は" "で区切る
        static int[] arrayint()
        {
            String[] input_line = Console.ReadLine().Split(' ');
            int[] input_num = new int[input_line.Length];
            for (int i = 0; i < input_line.Length; i++)
            {
                input_num[i] = int.Parse(input_line[i]);
            }
            return input_num;
        }
    }
}

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

int main() {
  ll n;
  cin >> n;
  vector<ll> p(n);
  for(ll i=0;i<n;i++) {
    cin >> p[i];
  }
  ll ans=0;
  for(ll i=1;i<n-1;i++) {
    if(p[i]>p[i-1]&&p[i]<p[i+1]){
      ans++;
    }
    if(p[i]<p[i-1]&&p[i]>p[i+1]){
      ans++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;


int N;
ll a[300];

int main(void) {
	cin >> N;
	rep(i, N) cin >> a[i];
	int ans = 0;
	while(1) {
		bool f = true;
		rep(i, N) if(a[i] % 2) f = false;
		if(f) ans++;
		else break;
		rep(i, N) a[i] /= 2;
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (n); ++i)
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;}
using namespace std;
using ll = long long;
using P = pair<int, int>;
using Pl = pair<long long, long long>;
using veci = vector<int>;
using vecl = vector<long long>;
using vecveci = vector<vector<int>>;
using vecvecl = vector<vector<long long>>;

int main() {
    int X,Y;
    cin >> X >> Y;
    for(int a = 0; a <= X; a++) {
        int b = X-a;
        if(2*a+4*b == Y) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
const int MAX1 = 1e5;
const int MAX2 = 1e4;
struct node {
    int id;
    node* next;
};
node* g[MAX1];
int c;
int color[MAX1];
bool visit[MAX1];
int n,m;
void dfs(int root, int c) {
    stack<int> s;
    s.push(root);
    visit[root] = true;
    color[root] = c;
    while(!s.empty()) {
        int x = s.top();
        node* p = g[x]->next;
        int flag = 0;
        while(p != NULL) {
            if(visit[p->id]==false) {
                flag = 1;
                s.push(p->id);
                visit[p->id] = true;
                color[p->id] = c;
                break;
            }
            p = p->next;
        }
        if(flag == 0) s.pop();

    }

}

bool reach(int s, int t) {
    return color[s] == color[t];
}
int main() {
    c = 0;// 代表颜色
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++) {
        visit[i] = false;
    }
    for(int i = 0; i < n; i++) {
        g[i] = (node*)malloc(sizeof(node));
        g[i]->next = NULL;
    }
    for(int i = 0; i < m; i++) {
        int s, t;
        scanf("%d %d", &s, &t);
        node* l = (node*)malloc(sizeof(node));
        l->id = t;
        l->next = NULL;
        node* p = g[s];
        while(p->next!=NULL) p = p->next;
        p->next = l;

        node* l2 = (node*)malloc(sizeof(node));
        l2->id = s;
        l2->next = NULL;
        node* p2 = g[t];
        while(p2->next!=NULL) p2 = p2->next;
        p2->next = l2;
    }
    for(int i = 0; i < n; i++) {
        if(visit[i] == false) {
            dfs(i, c);
            c++;
        }
    }
    int q;
    scanf("%d", &q);
    for(int i = 0; i < q; i++) {
        int s, t;
        scanf("%d %d", &s, &t);
        if(reach(s, t)) {
            printf("yes\n");
        } else {
            printf("no\n");
        }
    }
    return 0;
}




Measured memory_bytes: 14080
#include <stdio.h>
#include <string.h>



int main()
{

    int a,b,c,d,i,j;
    long long int x=1,y=1;
    scanf("%d %d", &a, &b);
    for(i=a;i>(a-2);i--)
    {
        x=x*i;
    }
    for(i=b;i>(b-2);i--)
    {
        y=y*i;
    }
    x=x/2;
    y=y/2;
    printf("%d\n",x+y);





    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define INF 1000000000
#define mod 998244353
using ll=long long;
const ll LINF=1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}

template<ll Mod>
struct ModInt{
    long long x;
    ModInt():x(0){}
    ModInt(long long y):x(y>=0?y%Mod:(Mod-(-y)%Mod)%Mod){}
    ModInt &operator+=(const ModInt &p){
        if((x+=p.x)>=Mod) x-=Mod;
        return *this;
    }
    ModInt &operator-=(const ModInt &p){
        if((x+=Mod-p.x)>=Mod)x-=Mod;
        return *this;
    }
    ModInt &operator*=(const ModInt &p){
        x=(int)(1ll*x*p.x%Mod);
        return *this;
    }
    ModInt &operator/=(const ModInt &p){
        (*this)*=p.inverse();
        return *this;
    }
    ModInt operator-()const{return ModInt(x);}
    ModInt operator+(const ModInt &p)const{return ModInt(*this)+=p;}
    ModInt operator-(const ModInt &p)const{return ModInt(*this)-=p;}
    ModInt operator*(const ModInt &p)const{return ModInt(*this)*=p;}
    ModInt operator/(const ModInt &p)const{return ModInt(*this)/=p;}
    ModInt operator==(const ModInt &p)const{return x==p.x;}
    ModInt operator!=(const ModInt &p)const{return x!=p.x;}
    ModInt inverse()const{
        int a=x,b=Mod,u=1,v=0,t;
        while(b>0){
            t=a/b;
            swap(a-=t*b,b);swap(u-=t*v,v);
        }
        return ModInt(u);
    }
    ModInt pow(long long n)const{
        ModInt ret(1),mul(x);
        while(n>0){
            if(n&1) ret*=mul;
            mul*=mul;n>>=1;
        }
        return ret;
    }
    friend ostream &operator<<(ostream &os,const ModInt &p){return os<<p.x;}
    friend istream &operator>>(istream &is,ModInt &a){long long t;is>>t;a=ModInt<Mod>(t);return (is);}
    static int get_mod(){return Mod;}
};
using mint=ModInt<mod>;


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

    int h,w,H,W;cin>>h>>w>>H>>W;
    mint dp[H][W];
    rep(i,H)rep(j,W)dp[i][j]=0;
    h--,w--;
    dp[h+1][w]=w+1;
    for(int i=h+2;i<H;i++){
        dp[i][w]=dp[i-1][w]*(w+1);
    }
    dp[h][w+1]=h+1;
    for(int j=w+2;j<W;j++){
        dp[h][j]=dp[h][j-1]*(h+1);
    }

    
    dp[h][w]=1;
    for(int i=h+1;i<H;i++){
        for(int j=w+1;j<W;j++){
            dp[i][j]=dp[i-1][j]*mint(j+1)+dp[i][j-1]*mint(i+1)-dp[i-1][j-1]*mint(i)*mint(j);
        }
    }

    // rep(i,H){
    //     rep(j,W){
    //         cout<<dp[i][j]<<"  ";
    //     }
    //     cout<<endl;
    // }
    cout<<dp[H-1][W-1]<<endl;
    return 0;
}


Measured memory_bytes: 73960
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,a,b) for(ll i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()

#define MAX_N 100002

//素数列挙(エラストテネスの篩)
//計算量O(n log log n)
int prime[MAX_N];
bool is_prime[MAX_N + 1];
bool is_prime2[MAX_N + 1];

//n以下の素数の数を返す
int sieve(int n){
    int p = 0;
    for(int i = 0; i <= n; i++) is_prime[i] = true;
    is_prime[0] = is_prime[1] = false;
    for(int i = 2; i <= n; i++){
        if(is_prime[i]){
            prime[p++] = i;
            for(int j = 2 * i; j <= n; j += i) is_prime[j] = false;
        }
    }
    return p;
}

int main(void){
    ll q;
    cin >> q;

    sieve(100002);

    rep(i, 0, MAX_N){
        if(is_prime[i] && is_prime[(i + 1) / 2]){
            is_prime2[i] = true;
        }else{
            is_prime2[i] = false;
        }
    }

    ll ans[MAX_N];
    ans[0] = 0;

    rep(i, 1, MAX_N){
        ans[i] = ans[i-1];
        if(is_prime2[i]){
            ans[i]++;
        }
    }

    pair<ll, ll> que[q];
    rep(i, 0, q){
        cin >> que[i].first >> que[i].second;
    }

    rep(i, 0, q){
        cout << ans[que[i].second] - ans[que[i].first - 1] << endl;
    }

}


Measured memory_bytes: 3200
#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
using namespace std;

struct Event{
    int time,diff;
    Event(int t,int d) : time(t), diff(d) {;}
};

bool operator<(const Event &e,const Event &f) {
    return e.time < f.time;
}

int n;
double l;
vector<Event> ev;

bool simulate(double pump) {
    double tank = l,vol = pump;
    int t = 0;

    // cout<<"pump = "<<pump<<endl;
    // cout<<tank<<endl;
    //first day
    for(int i=0; i<ev.size(); ++i) {
        tank = min(tank + vol * (ev[i].time - t), l);
        if(tank <= 0) return false;
        vol += ev[i].diff;
        t = ev[i].time;
    }
    tank = min(tank + vol * (86400 - t), l);

    // cout<<tank<<endl;
    // cout<<"end first day"<<endl;
    //second day
    double sf = tank;
    vol = pump; t = 0;

    for(int i=0; i<ev.size(); ++i) {
        tank = min(tank + vol * (ev[i].time - t), l);
        if(tank <= 0) {
            return false;
        }
        vol += ev[i].diff;
        t = ev[i].time;
    }
    tank = min(tank + vol * (86400 - t), l);

    return (tank >= sf);
}

const double eps = 1e-7;

int main() {
    int s,t,u;
    while(cin>>n>>l) {
        if(n == 0 && l == 0.0) break;
        ev.clear();
        double lo = 0.0,hi = l;
        for(int i=0; i<n; ++i) {
            cin>>s>>t>>u;
            ev.push_back(Event(s,-u));
            ev.push_back(Event(t,u));
            hi = max((double)u, hi);
        }

        while(lo + eps < hi) {
            double mid = (lo + hi)/2;
            bool mm;
            if(mm = simulate(mid)) hi = mid;
            else lo = mid;
            //cout<<mid<<" : "<<mm<<endl;
        }
        printf("%.6f\n", lo);
    }
}

Measured memory_bytes: 2456
//#define DEBUG
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
using namespace std;

#define BSET(a, p) ((a) | (1ll << (p)))
#define BCHK(a, p) ((a) & (1ll << (p)))
#define BXOR(a, p) ((a) ^ (1ll << (p)));
#define BREM(a, p) (BCHK(a, p)?(BXOR(a, p)):(a))
#define BSHO(a, N) (bitset<N>(a))

#define fi first
#define sc second 
#define pb push_back


#ifdef DEBUG
    #define dbg(s) {s;}
    #define PRELUDE
#endif

#ifndef DEBUG 
    #define PRELUDE { ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0); }
    #define dbg(s)
    #define endl "\n"
#endif

#define int ll
#define i32 int32_t

#define RBTTYPE int
#define ordered_set tree<RBTTYPE, null_type, less<RBTTYPE>, rb_tree_tag,tree_order_statistics_node_update> 
// Ordered set docs:
// order_of_key (k) : Number of items strictly smaller than k .
// find_by_order(k) : K-th element in a set (counting from zero).

#define all(v) (v).begin(),(v).end()

typedef long long ll;
typedef long double ld;
typedef pair< int, int > pii;
typedef pair< ll, ll > pll;

// To remove randomization use 0 below:
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int ri(int x) { // from [0, n-1]
    return uniform_int_distribution<int>(0, x - 1)(rng);
}

inline ld rf() { // from [0, 1]
    return uniform_real_distribution<ld>(0, 1)(rng);
}

ll gcd(ll x, ll y) {
    if (x < y) return gcd(y, x);
    if (y == 0) return x;
    return gcd(y, x % y);
} 

const ll mod = 1e9 + 7;

ll modexp(ll x, ll ex) {
    x = x%mod;
    ex = ex % (mod-1);
    ll ans = 1ll;
    while (ex > 0) {
        if (ex & 1ll) ans = (ans * x) % mod;
        ex >>= 1ll;
        x = (x * x) % mod;
    }
    return ans;
}

const int maxn = 4e2 + 7;

const ll inf = 1e17 + 7;

int a[maxn];
int presum[maxn];

int ans[maxn][maxn];

void solve()
{
    int n;
    cin>>n;
    presum[0] = 0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        presum[i] = presum[i-1] + a[i];
    }

    memset(ans,0,sizeof(ans));

    int en,sum;
    for(int siz = 2;siz<=n;siz++)
    {
        for(int st = 1;st<=n;st++)
        {
            en = st+siz-1;
            if(en>n)
                continue;
            ans[st][en] = inf;
            sum = presum[en]-presum[st-1];
            for(int k=st;k<en;k++)
            {
                ans[st][en] = min(ans[st][en],sum + ans[st][k] + ans[k+1][en]);
            }
            //cout<<st<<","<<en<<" -> "<<ans[st][en]<<endl;
        }
    }

    cout<<ans[1][n]<<endl;
}

i32 main() {
    //freopen("<file>.in", "r", stdin);
    //freopen("<file>.out", "w", stdout);
    
    PRELUDE;
    int t = 1;
    //cin>>t;
    while(t--)
        solve();
}


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

int main(){
  int n, k;
  cin >> n >> k;
  vector<int> p[n+1];
  rep(i, n-1){
    int a, b;
    cin >> a >> b;
    p[a].push_back(b);
    p[b].push_back(a);
  }
  bool used[n+1];
  rep(i, n+1) used[i] = false;
  ll ans = 1;
  queue<P> que;
  que.push(P(1,k));
  used[1] = true;
  while(!que.empty()){
    P q = que.front(); que.pop();
    int c = q.first;
    ans = (ans * q.second) % mod;
    int u = 0, nu = 1;
    rep(i, p[c].size()) if(used[p[c][i]]) u++;
    rep(i, p[c].size()){
      if(!used[p[c][i]]){
        if(k-nu-u < 0) que.push(P(p[c][i],0));
        else que.push(P(p[c][i], k-nu-u));
        nu++;
        used[p[c][i]] = true;
      }
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 7032
#include<bits/stdc++.h>
#define debug(x) cout << #x << " = " << x << endl
typedef unsigned long long ull;
typedef long long ll;
using namespace std;
const int N=100000;
int a[N],n,m,x,y,z;
int main()
{
	cin >> n>>m;

	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=n;j++)
		{
			z=(n-i)-j;
			if((i*10000)+(j*5000)+(z*1000)==m&&z>=0)
			{
				cout << i<<" "<<j<<" "<<z;
				return 0;
			}
		}
	}
	cout << -1<<" "<< -1 <<" "<< -1;
		
	
}


Measured memory_bytes: 256
public class Main {

	public static void main(String[] args) {
		for (int i = 1; i <= 9; i++) {
			for (int j = 1; j <= 9; j++) {
				int answer = i * j;

				System.out.println(i + "x" + j + "=" + answer);
			}
		}
	}

}

Measured memory_bytes: 16856
import numpy as np
from collections import defaultdict
from math import gcd
import time
import sys
from collections import Counter
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
start = time.time()
N = int(input())
s = set()
for i in range(N):
    s.add(input())

print(len(s))


Measured memory_bytes: 49084
#include <algorithm>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

typedef long long ll;

#define rep(i, a, b) for (ll i = a; i < (ll)b; ++i)
#define digit(a) to_string(a).size()
#define INF 10e12
#define MAX 51000
#define all(x) (x).begin(), (x).end()
#define MX(x) *max_element(all(x))
#define MN(x) *min_element(all(x))

using namespace std;

const long long MOD = 1e9 + 7;

int main(void)
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    ll x, y;
    cin >> x >> y;
    ll ans = 0;
    while (x <= y)
    {
        ++ans;
        x *= 2;
    }
    cout << ans << endl;
}

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


int main() {
	int n;
  	std::cin >> n;
  	std::vector<int> arr(n + 1), dp;
  	for(int i = 1; i <= n; i++)
      std::cin >> arr[i];
  
  	dp.assign(n + 1, INT32_MAX);
  	
  	dp[1] = 0;
  
  	for(int i = 2; i <= n; i++)
    	for(int j : {i - 1, i - 2})
        	if(j > 0)
              dp[i] = std::min(dp[i], std::abs(arr[j] - arr[i]) + dp[j]);
  	std::cout << dp[n];
}

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

int main() {

	int N,x=0,Xmax=0;
  string S;
	cin>>N>>S;
  
  for(int i=0; i<N; i++){
    if(S.at(i)=='I'){x++;}
    else if(S.at(i)=='D'){x--;}
    if(Xmax<x){Xmax=x;}
  }
	
	cout<<Xmax<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
    if(a%2==0){
        if(a/2>=b) cout<<"YES\n";
        else cout<<"NO\n";
    }
    else{
        if(a/2+1>=b) cout<<"YES";
        else cout<<"NO\n";
    }
}


Measured memory_bytes: 764
from sys import stdin
import sys
import numpy as np
import collections
from functools import cmp_to_key
import heapq

##  input functions for me
def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return map(int, input().split()) 
    else: return map(int, input().split(sep))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()
##
def main():
    s = rs()
    print(chr(ord(s[0])+1))


if __name__ == "__main__":
    main()


Measured memory_bytes: 12492
using System;
using System.Linq;
using System.Collections.Generic;
using System.IO;
using static System.Console;


namespace atcorder2
{
    class Program
    {
        public static long Read()
        {

            return long.Parse(Console.ReadLine());
        }

        public static long[] Reads()
        {
            return Console.ReadLine().Split().Select(long.Parse).ToArray();
        }

       
       
        public static long gcd(long x,long y)
        {
            if (x < y) gcd(y, x);
            
            while (y > 0)
            {
                var z = x % y;
                x = y;
                y = z;
            }
            return x;
        }

        public static long lcm(long x,long y)
        {
            return x * y / gcd(x, y);
        }



        static void Main(string[] args)
        {
            var sw = new StreamWriter(OpenStandardOutput()) { AutoFlush = false };
            SetOut(sw);


            var nm = Reads();
            var n = nm[0];
            var m = nm[1];
            var h = Reads();
            var ans = new bool[n];
            var a = new long[n];
            var b = new long[n];
            for (int i = 0; i <m ; i++)
            {
                var ab = Reads();
                if (h[ab[0]-1] > h[ab[1]-1]) ans[ab[1] - 1] = true;
                else if (h[ab[0]-1] < h[ab[1]-1]) ans[ab[0]-1] = true;
                else
                {
                    ans[ab[0]-1] = true;
                    ans[ab[1]-1] = true;
                }
            }
            long res = 0;
            for (int i = 0; i < n; i++)
            {
                if (!ans[i]) res++;
            }
            WriteLine(res);

           
          
            Out.Flush();
        }
    }
}




Measured memory_bytes: 35288
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> Gre;
const int N=1<<18;
int A,B,pA,pB;
#define lowbit(a) ((a)&(-a))
int Cnt[N],bits[20],Ful=0;
int n;
inline void Solve(int Xor,int A,int sum){
	if(!(Cnt[sum^Ful]^1)) {printf("%d %d ",A,A^Xor);return;}
	for(int i=0;i<n;++i){
		if(!(sum&bits[i])&&(Xor&bits[i])){
			for(int j=0;j<n;++j) {
				if(i==j) continue;
				if(!(sum&bits[j])){
					Solve(bits[j],A,sum|bits[i]);
					Solve(Xor^bits[j]^bits[i],A^bits[i]^bits[j],sum|bits[i]);
					return;
				}
			}
		}
	}
}
int main()
{
    cin>>n>>A>>B;
	int len=1<<n;Ful=len-1;bits[0]=1;
	for(int i=0;i<len;++i) Cnt[i]=Cnt[i>>1]+(i&1);
	for(int i=1;i<=18;++i) bits[i]=bits[i-1]<<1;
	int res=A^B;
	if(Cnt[res]&1) puts("YES"),Solve(res,A,0);
	else puts("NO");
    return 0;
}


Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pint = pair<int, int>;
using pll = pair<ll, ll>;
using Edge = pair<int, ll>;
using Graph = vector<vector<int>>;
using WeightedGraph = vector<vector<Edge>>;
const ll INF64 = 1LL << 60;
const int INF32 = 1 << 29;
const ll MOD = 1000000007;

const int CASES = 3;

void solve() {
    ll a, b; cin >> a >> b;
    if(a > b) swap(a,b);
    int ans = 3;
    if(a == 1 && b == 2) ans = 3;
    if(a == 1 && b == 3) ans = 2;
    if(a == 2 && b == 3) ans = 1;
    cout << ans << endl;
}

int main() {
#ifdef MYLOCAL
    vector<string> filenames {"input1.txt", "input2.txt", "input3.txt", "input4.txt"};
    cout << "------------\n";
    for(int i = 0; i < CASES; ++i){
        ifstream in(filenames[i]);
        cin.rdbuf(in.rdbuf());
        solve();
        cout << "------------\n";
    }
#else

    solve();

#endif
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<map>
#include<iomanip>
#include<limits>
#include<queue>
#include<set>

using namespace std;


int main(){


	int N,M;
	cin >> N >> M;

	if(M < N){
		swap(N,M);
	}

	if(N == 1 && M == 1){
		cout << 1 << endl;
	}else if(N == 1 && M >=2){
		cout << M - 2 << endl;
	}else if(N>=2 && M >=2){
		cout << (long long)(N-2)*(M-2) << endl;
	}


	return 0;

}


Measured memory_bytes: 256
//Utkarsh-raj

#include<bits/stdc++.h>

#define ll long long int
#define vc vector
#define mod 1000000007
#define mp make_pair
#define pb push_back
#define nl cout<<endl;
#define ff first
#define ss second

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    ifstream myFile("task.in");
    if(!myFile.fail())
    {
        assert(freopen("task.in", "r", stdin));
    }

    ll n, k;
    cin>>n>>k;

    ll arr[n+1];
    for(ll i=1; i<=n; i++){
        cin>>arr[i];
    }

    if(k == 0){
        cout<<1<<endl;
        return 0;
    }

    vector<vector<ll> > dp(n+1, vector<ll> (k+1, 0));

    for(ll i=0; i<=n; i++){
        dp[i][0] = 1;
    }

    for(ll j=0; j<=k; j++){
        dp[0][j] = 1;
    }

    // for(ll i=1; i<=n; i++){
    //     for(ll j=1; j<=k; j++){
    //         for(ll k=0; k<=arr[i]; k++){
    //             if(j >= k)
    //                 dp[i][j] += dp[i-1][j - k];
    //         }
    //     }
    // }

    for(ll i=1; i<=n; i++){
        for(ll j=1; j<=k; j++){
            ll x = max(j - arr[i], (ll)0);

            if(x == 0){
                dp[i][j] = (dp[i][j-1]%mod + dp[i-1][j]%mod)%mod;
            }
            else{
                ll y = (dp[i-1][j]%mod - dp[i-1][x-1]%mod + mod)%mod;
                dp[i][j] = (dp[i][j-1]%mod + y%mod)%mod;
            }
        }
    }

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

    ll y = (dp[n][k]%mod - dp[n][k-1]%mod + mod)%mod;

    cout<<y<<endl;

    return 0;
}


Measured memory_bytes: 83188
N, M = map(int, input().split())
X, Y = [], []

for _ in range(M):
    x, y = map(int, input().split())
    X.append(x - 1)
    Y.append(y - 1)

red = [0] * N
red[0] = 1
ball = [1] * N

for x, y in zip(X, Y):
    if red[x] == 1 and ball[x] != 0:
        red[y] = 1
        if ball[x] == 1:
            red[x] = 0
        ball[x] -= 1
        ball[y] += 1
    elif ball[x] != 0:
        ball[x] -= 1
        ball[y] += 1

print(sum(red))


Measured memory_bytes: 12528
import java.util.HashSet;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);
		int n;
		while((n = scan.nextInt()) != 0){
			int[][] matrix = new int[n][n];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					matrix[i][j] = scan.nextInt();
				}
			}

			HashSet<Integer> set = new HashSet<Integer>();

			Loop:for (int i = 0; i < n; i++) {

				int min = -1;
				for (int j = 0; j < n ; j++) {
					if(min==-1 || min>matrix[i][j]) min = matrix[i][j];
				}
				for (int j = 0; j < n; j++) {
					if(min==matrix[i][j]){
						int no = i*n+j;
						if(set.contains(no)) {
							System.out.println(matrix[no/n][no%n]);
							break Loop;
						}
						set.add(no);
					}
				}

				int max = 0;
				for (int j = 0; j < n; j++) {
					if(max<matrix[j][i]) max = matrix[j][i];
				}
				for (int j = 0; j < n; j++) {
					if(max==matrix[j][i]){
						int no = i+j*n;
						if(set.contains(no)) {
							System.out.println(matrix[no/n][no%n]);
							break Loop;
						}
						set.add(no);
					}
				}

				if(i==n-1) System.out.println(0);
			}
		}
	}
}

Measured memory_bytes: 19516
#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
 
const int N = 1e5 + 5;


int32_t main()
{
   IOS;
   int a;
   cin >> a;

   cout << a+(a*a)+(a*a*a) << endl;
   


   return 0;
}
 

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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
string char_to_string(char val) {
    return string(1, val);
}
int char_to_int(char val) {
    return val - '0';
}

ll combi3(ll a) {
  return (a * (a - 1) * (a - 2)) / 6;
}

ll combi2(ll a) {
  return (a * (a - 1)) / 2;
}

int main() {
    int N; cin >> N;
    vector<string> S(N); REP(i, N) cin >> S[i];

    map<char, ll> m;
    m['M'] = 0;
    m['A'] = 0;
    m['R'] = 0;
    m['C'] = 0;
    m['H'] = 0;

    REP(i, N) {
      if(S[i].at(0) == 'M') m['M']++;
      if(S[i].at(0) == 'A') m['A']++;
      if(S[i].at(0) == 'R') m['R']++;
      if(S[i].at(0) == 'C') m['C']++;
      if(S[i].at(0) == 'H') m['H']++;
    }

    ll A = 0;
    if(m['M'] > 2) A += combi3(m['M']);
    if(m['A'] > 2) A += combi3(m['A']);
    if(m['R'] > 2) A += combi3(m['R']);
    if(m['C'] > 2) A += combi3(m['C']);
    if(m['H'] > 2) A += combi3(m['H']);

    ll B = 0;
    if(m['M'] > 1) B += combi2(m['M']) * (m['A'] + m['R'] + m['C'] + m['H']);
    if(m['A'] > 1) B += combi2(m['A']) * (m['M'] + m['R'] + m['C'] + m['H']);
    if(m['R'] > 1) B += combi2(m['R']) * (m['M'] + m['A'] + m['C'] + m['H']);
    if(m['C'] > 1) B += combi2(m['C']) * (m['M'] + m['A'] + m['R'] + m['H']);
    if(m['H'] > 1) B += combi2(m['H']) * (m['M'] + m['A'] + m['R'] + m['C']);
    
    ll C = combi3(m['M'] + m['A'] + m['R'] + m['C'] + m['H']);
    cout << C - A - B << endl;
}

Measured memory_bytes: 6144
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repi(i, n) for (int i = 1; i <= (n); i++)
#define pp(v) cout << #v << "=" << (v) << endl;
#define div_ceil(a,b) ((a) + ((b) - 1)) / (b)

// ABC115 C
// 方針
// 高さを並べ替えて差分数列[df]を作る
// 差分数列の累積和[cs]を作る
// 連続するK-1個の区間和の最小をもとめる
// 計算量は並べ替えに依存するのでO(NlogN)

int main() {
  int n,k; cin >> n >> k;
  vector<int> h(n);
  rep(i,n) cin >> h[i];
  sort(h.begin(), h.end());

  // 差分数列
  vector<int> df(n-1);
  rep(i,n-1) df[i] = h[i+1] - h[i];

  // 差分数列の累積和
  vector<int> cs(n);
  rep(i,n) cs[i+1] = cs[i] + df[i];

  //
  int ans = 1e9;
  rep(i,n-k+1) {
    int diff = cs[i+k-1] - cs[i];
    ans = min(ans, diff);
  }

  cout << ans << endl;
}


Measured memory_bytes: 1408
N = int(input())
for a in range(1,3501):
    for b in range(a,3501):
        m =  (4*a*b) - N*(a+b)
        if m> 0 and N*a*b % m == 0:
            c = (N*a*b)//m
            break
    else:
        continue
    break
print(a,b,c)


Measured memory_bytes: 2940
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
int main(void){
    ll n,ans = 0;
    cin >> n;
    vector<ll> a(n),b(n),c(n);
    for(int i = 0;i < n;i++) cin >> a[i];
    for(int i = 0;i < n;i++) cin >> b[i];
    for(int i = 0;i < n;i++) cin >> c[i];
    
    sort(a.begin(),a.end());
    sort(c.begin(),c.end());
    for(int i = 0;i < n;i++){
        auto it1 = lower_bound(a.begin(),a.end(),b[i]);
        auto it2 = upper_bound(c.begin(),c.end(),b[i]);
        ll d1 = distance(a.begin(),it1);
        ll d2 = distance(it2,c.end());
        ans += (d1*d2);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
	using namespace std;
	#define ll long long int
	#define mp make_pair
	#define pb push_back
	#define pll pair<ll,ll>
	ll INF = 1000000007;


	/***************/
	 #define amin main
	/***************/

	ll exp(ll x, ll n)
	{if(n==0) return 1;if(n==1) return x%INF;if(n%2==0) return exp((x*x)%INF,n/2); else return(x*exp((x*x)%INF,n/2))%INF;}


	int amin()
	{
		ll t,i;
		ios_base::sync_with_stdio(false);
		cin.tie(NULL);
		ll h,m,a,b,k;
		cin>>h>>m>>a>>b>>k;
		ll sum =0;
		if(h>a)
		{
			sum += (24-h+a)*60 + b-m;
		}
		else
		 sum += abs(h-a)*60 + b-m;
		if(sum-k<0)
			cout<<0<<endl;
		else
		cout<<sum-k<<endl;

		
		

		
		


		
		return 0;
	}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
// #include "../cxx-prettyprint/prettyprint.hpp" // vecの内容をきれいに表示
 
using namespace std;
typedef long long ll;
 
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, m, n) for(int i = m;i < n;i++)
 
// 今回は関数でdpテーブルをいじるのでグローバル
vector<int> dp(100001,0);
vector<bool> flg(100001, false);
vector< vector<int> > A(100001,vector<int>(0));
 
int f(int x){
	// すでに探索完了ならその値を返す
	if(flg[x]) return dp[x];
	flg[x] = true;
	// 探索
	int fans = dp[x]; // 経路の長さ
	for(const auto y : A[x]){
		// cout << y;
		fans = max(fans, f(y) + 1);
	}
	// cout << "\n";
	return dp[x] = fans;
}
 
int main(){
// ここに処理を記述
 
	int N, M;
	cin >> N >> M;
 
	int x, y;
	for(int i=0; i<M; i++){
		cin >> x >> y;
		A[x].push_back(y);
	}
 
	// DAG(閉路なし有向グラフ)はトポロジカルソートでDP可能性あり
	// 今回はそうじゃなくてメモ化再帰で記述
	// f(x) : xを始点とする最長経路
	// f(x) = 0(xの行先なし) or max(f(y)+1|x->yが存在するy)
	// この時答えはmax(f(x))
	int ans = 0;
	FOR(i,1,N+1){
		ans = max(ans,f(i));
	}
 
	// cout << dp << "\n";
 
	cout << ans << "\n";
 
return 0;
}

Measured memory_bytes: 8192
import static java.util.Arrays.deepToString;

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		new Main().run();
	}
	void tr(Object... os) {
		System.err.println(deepToString(os));
	}

	Scanner sc = new Scanner(System.in);
	public void run() {
		makePrimes();
		for (;sc.hasNext();) {
			int n = sc.nextInt();
			if (n <= 0) break;
			int res = 0;
			for (int i = 0; n - primes[i] >= primes[i]; i++) {
				if (isPrime[n - primes[i]]) ++res;
			}
			System.out.println(res);
		}
	}
	
	static final int MAX_N = 1024 * 1024;
	boolean[] isPrime = new boolean[MAX_N];
	int[] primes;
	void makePrimes(){
		if (primes != null) return;
		for (int i = 0; i < isPrime.length; i++) isPrime[i] = true;
		isPrime[0] = isPrime[1] = false;
		for (int i = 2; i * i < isPrime.length; i++)
			if (isPrime[i])
				for(int j = i * i; j < isPrime.length; j += i)
					isPrime[j] = false;
		int p = 0;
		for (int i = 2; i < isPrime.length; i++) p += isPrime[i] ? 1 : 0;
		primes = new int[p];
		p = 0;
		for (int i = 2; i < isPrime.length; i++) if (isPrime[i]) primes[p++] = i;
	}

}

Measured memory_bytes: 23988
#include<stdio.h>
#define INF 100000000
int le[200][200];
int se[200][200];
int dp[2][200];
int q[1000];
int min(int a,int b){return a<b?a:b;}
int main(){
	int n,m;
	int i,j,k;
	while(1){
	scanf("%d %d",&n,&m);
	if(n==0)return 0;
	for(i=0;i<200;i++){
		for(j=0;j<200;j++){
			le[i][j]=INF;
			se[i][j]=INF;
		}
		le[i][i]=0;
		se[i][i]=0;
	}
	for(i=0;i<m;i++){
		int a,b,c;
		char t;
		scanf("%d %d %d %c\n",&a,&b,&c,&t);
		a--;b--;
		if(t=='L'){
			le[a][b]=min(le[a][b],c);
			le[b][a]=min(le[b][a],c);
		}
		else{
			se[a][b]=min(se[a][b],c);
			se[b][a]=min(se[b][a],c);
		}
	}
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			for(k=0;k<n;k++){
				le[j][k]=min(le[j][k],le[j][i]+le[i][k]);
				se[j][k]=min(se[j][k],se[j][i]+se[i][k]);
			}
		}
	}
	int nq;
	scanf("%d",&nq);
	for(i=0;i<nq;i++){
		scanf("%d",&q[i]);
		q[i]--;
	}
	for(i=0;i<200;i++)dp[0][i]=INF;
	dp[0][q[0]]=0;
	for(i=1;i<nq;i++){
		for(j=0;j<200;j++)dp[i%2][j]=INF;
		for(j=0;j<n;j++){
			for(k=0;k<n;k++){
				dp[i%2][k]=min(dp[i%2][k],dp[(i+1)%2][j]+le[q[i-1]][j]+se[j][k]+le[k][q[i]]);
			}
			dp[i%2][j]=min(dp[i%2][j],dp[(i+1)%2][j]+le[q[i-1]][q[i]]);
		}
	}
	int ans=INF;
	for(i=0;i<n;i++)ans=min(ans,dp[(nq+1)%2][i]);
	printf("%d\n",ans);
	}
}

Measured memory_bytes: 1348
import java.math.*;
import java.util.*;
import java.util.function.*;
 
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    List<BigInteger> A = new LinkedList<>();
    for (int i = 0; i < N; i++) A.add(BigInteger.valueOf(sc.nextInt()));
    sc.close();

    BigInteger lcm = A.stream().parallel()
      .reduce(BigInteger.ONE, (a, b) -> a.divide(a.gcd(b)).multiply(b));

    BigInteger ans = A.stream().parallel()
      .map(a -> lcm.divide(a))
      .reduce(BigInteger.ZERO, (a, b) -> a.add(b));

    BigInteger mod = BigInteger.valueOf(1000000007);
    System.out.println(ans.mod(mod));
  }
}

Measured memory_bytes: 193144
#include<cstdio>
#include<iostream>
#include<string>
#include<set>
#include<map>
#include<vector>
#include<deque>
#include<tuple>
#include<algorithm>
#include<numeric>
#include<limits>
#include<boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
using namespace std;
#define BEGIN ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define END return EXIT_SUCCESS
#define rep(I,N) for(auto I=0;I<(N);++I)
#define up(I,A,B) for(auto I=(A);I<=(B);++I)
#define dw(I,A,B) for(auto I=(A);I>=(B);--I)
#define all(C) (C).begin(),(C).end()
#define rall(C) (C).rbegin(),(C).rend()
#define ft first
#define sd second
#define mp make_pair
#define mt make_tuple
#define pf push_front
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define rs resize
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
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;}
template<class T>inline void                                      in(T &p){cin>>p;}
template<class T1,class T2>inline void                            in(T1 &p1,T2 &p2){cin>>p1>>p2;}
template<class T1,class T2,class T3>inline void                   in(T1 &p1,T2 &p2,T3 &p3){cin>>p1>>p2>>p3;}
template<class T1,class T2,class T3,class T4>inline void          in(T1 &p1,T2 &p2,T3 &p3,T4 &p4){cin>>p1>>p2>>p3>>p4;}
template<class T1,class T2,class T3,class T4,class T5>inline void in(T1 &p1,T2 &p2,T3 &p3,T4 &p4,T5 &p5){cin>>p1>>p2>>p3>>p4>>p5;}
template<class T>inline void                                      ins(T &p){for_each(all(p),in<decltype(p[0])>);}
template<class T>inline void                             out(T p){cout<<p<<endl;}
template<class T1,class T2>inline void                   out(T1 p1,T2 p2){cout<<p1<<" "<<p2<<endl;}
template<class T1,class T2,class T3>inline void          out(T1 p1,T2 p2,T3 p3){cout<<p1<<" "<<p2<<" "<<p3<<endl;}
template<class T1,class T2,class T3,class T4>inline void out(T1 p1,T2 p2,T3 p3,T4 p4){cout<<p1<<" "<<p2<<" "<<p3<<" "<<p4<<endl;}
inline                                              void out(double p){printf("%.10f\n",p);}
template<class T>inline                             void outs(T p){for_each(all(p),out<decltype(p[0])>);}
template<class T>inline void outs(vector<T> V){int n=V.size();rep(i,n)cout<<V[i]<<" \n"[i==n-1];}
long rec(long N,long K){
  if(N<=abs(N-K))return N;
  else {
    if(N<K) return rec(K%N,K);
    else return rec(N%K,K);
  }
}
inline void solve(void){
  long N,K;in(N,K);
  out(rec(N,K));
}
int main(int argc,char**argv){
  BEGIN;
  solve();
  END;
}


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

int main() {
  double N;
  cin >> N;
  if (N >= 2) {
    if (fmod(N, 2) == 0)
      cout << "0.5" << endl;
    else
      cout << 1 - (((N - 1) / 2) / N) << endl;
  } else {
    cout << "1" << endl;
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
int main()
{
    std::size_t N, H, W, A, B, ans{};
    std::cin >> N >> H >> W;
    
    for (std::size_t i{}; i < N; ++i)
    {
        std::cin >> A >> B;
        if (H <= A && W <= B) ans++;
    }
    std::cout << ans << std::endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
#include <stack>
#include <set>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define INF (int)(1123456789)
#define LINF (long long int)(112345678901234567)
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define all(v) v.begin(), v.end()

const int N = (int)3e5+3;

ll mpow(ll a, ll b){
	if(b==0) return 1;
	else if(b%2==0){ll memo = mpow(a,b/2); return memo*memo%MOD;}
	else return mpow(a,b-1) * a % MOD;
}
ll gcd(ll a, ll b){
	if(b==0) return a;
	else return gcd(b, a%b);
}
vector<ll> kaijo_memo;
ll kaijo(ll n){
	if(kaijo_memo.size() > n) return kaijo_memo[n];
	if(kaijo_memo.size() == 0) kaijo_memo.push_back(1);
	while(kaijo_memo.size() <= n) kaijo_memo.push_back(kaijo_memo[kaijo_memo.size()-1] * kaijo_memo.size() % MOD);
	return kaijo_memo[n];
}
ll nCr(ll n, ll r){
	if(n < r || r < 0) return 0;
	ll ret = 1;
	ret *= kaijo(n); ret %= MOD;
	ret *= mpow(kaijo(r), MOD-2); ret %= MOD;
	ret *= mpow(kaijo(n-r), MOD-2); ret %= MOD;
	return ret;
}

int main(void){
	map<int,int> m;
	int n;cin>>n;
	rep(i,n){
		int a;cin>>a;
		if(m.count(a) == 0){
			m[a] = 1;
		}else{
			m[a]++;
		}
	}
	ll ans = 0;
	for(auto p : m){
		int key = p.first; int value = p.second;
		if(key <= value){
			ans += value - key;
		}else{
			ans += value;
		}
	}
	cout<<ans<<endl;
	return 0;
}


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

int main() {
	int w, h, x, y;
	cin >> w >> h >> x >> y;
	double ans = (double)w*h/2;
	int num = (w == x * 2 && h == y * 2) ? 1 : 0;
	printf("%.10f %d\n", ans, num);
	return 0;
}

Measured memory_bytes: 256
import java.util.*;

class Main{
    public static int abs(int a){
        return (a>0)?a:(-a);
    }
    
    public static int min(int a,int b){
        return (a<b)?a:b;
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        int K=sc.nextInt();
        int[] x=new int[N];
        
        for(int i=0;i<N;i++){
            x[i]=sc.nextInt();
        }
        
        int ans=1000000000;
        
        for(int i=0;i<N-K+1;i++){
            int tmp=abs(x[i]-x[i+K-1])+min(abs(x[i]),abs(x[i+K-1]));
            if(ans>tmp){
                ans=tmp;
            }
        }
        
        System.out.println(ans);
    }
}

Measured memory_bytes: 49676
import java.util.*;

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

    char[][] figure = new char[H][W];
    List<Integer> Hlist = new ArrayList<Integer>();
    List<Integer> Wlist = new ArrayList<Integer>();
    for(int i=0;i<H;i++){
      String s = sc.next();
      if(s.contains("#")){
        Hlist.add(i);
      }
      for(int j=0;j<W;j++){
        figure[i][j]=s.charAt(j);
      }
    }


    for(int i=0;i<W;i++){
      boolean contain_s = false;
      for(int j=0;j<H;j++){
        if(figure[j][i]=='#'){
          contain_s =true;
          break;
        }
      }
      if(contain_s){
        Wlist.add(i);
      }
    }

    for(int h : Hlist){
      for(int w : Wlist){
        System.out.print(figure[h][w]);
      }
      System.out.println("");
    }
  }
}


Measured memory_bytes: 24864
#rip this is hard 

def read_input():
  l = [int(item) for item in input().split()]
  sx = l[0]
  sy = l[1]
  tx = l[2]
  ty = l[3]
  return sx,sy,tx,ty

def main():
  sx,sy,tx,ty = read_input()
  dx = tx - sx
  dy = ty - sy
  s = ''
  s+='U'*dy+'R'*dx
  s+='D'*dy+'L'*dx
  s+='L'+'U'*(dy+1)+'R'*(dx+1)+'D'
  s+='R'+'D'*(dy+1)+'L'*(dx+1)+'U'
  print(s)

  

if __name__ == '__main__':
  main()

Measured memory_bytes: 3064
#include <iostream>
#include <utility>
#include <cstdlib>

using namespace std;

int64_t gcd(int64_t x, int64_t y) {
  if (x < y) swap(x, y);
  while (y) {
    x = exchange(y, x % y);
  }
  return x;
}

int main() {
  int64_t K;
  cin >> K;
  int64_t result = 0;
  for (int64_t a = 1; a <= K; ++a) {
    for (int64_t b = 1; b <= K; ++b) {
      for (int64_t c = 1; c <= K; ++c) {
        result += gcd(a, gcd(b, c));
      }
    }
  }
  cout << result << endl;
  return 0;
}


Measured memory_bytes: 3600