akhauriyash/Code-Regression huggingface dataset:
import math

line = input()
px, py = list(map(int, line.split()))
line = input()
cx, cy, r = list(map(int, line.split()))

def solve():
    d2 = (px - cx)*(px - cx) + (py - cy)*(py - cy)
    d = math.sqrt(d2)
    sine = r / d
    sin2 = r * r / d2
    cosine = math.sqrt(1 - sin2)
    cos2 = 1 - sin2
    x1 = (cx - px) * cos2 - (cy - py) * sine * cosine + px
    y1 = (cx - px) * sine * cosine + (cy - py) * cos2 + py
    x2 = (cx - px) * cos2 + (cy - py) * sine * cosine + px
    y2 = - (cx - px) * sine * cosine + (cy - py) * cos2 + py
    if x1 > x2:
        x1, x2 = x2, x1
        y1, y2 = y2, y1
    print(x1, y1)
    print(x2, y2)

solve()



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

ll const INF=1e18+5;
//we flip the table, i.e. the relation/mapping/change the defintion

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll N,W; cin>>N>>W;
    ll val[N],wt[N];
    
    //definition of dp[i], changed to: 
    //dp[i] gives the minimum total weight of items with exactly i value 
    ll sum_value=0; //range 0 to max Value posible in knapsack
    for (ll in=0;in<N;in++) {
        ll weight,value; cin>>weight>>value;
        sum_value+=value;
        wt[in]=weight; val[in]=value;
    }
    
    ll dp[sum_value+1];
    for (ll i1=0;i1<=sum_value;i1++) dp[i1]=INF; //initialisation
    dp[0]=0; //obviously
    
    for (ll i=0;i<N;i++) { //i is item
        for (ll j=sum_value;j>=val[i];j--) 
            dp[j]=min(dp[j], dp[j-val[i]]+wt[i]);
            //dont choose^    choose^ opt ans will be state without having this value + abhi ka weight since we're choose
    }
    
    ll ans=0;
    for (ll i=0;i<=sum_value;i++) {
        if (dp[i]<=W)
            ans=max(ans, i); //since i here is the max value we can get while not exceeding W 
    }
    
    cout<<ans<<"\n";
    return 0;
}

Measured memory_bytes: 1024
#include<cstdio>
#include<algorithm>
const int M=100010,mod=1000000007;
typedef long long ll;
int n,m,a[M];
struct Matrix{
	int a[4][4];
	int* operator[](int x){
		return a[x];
	}
};
Matrix mul(Matrix x,Matrix y,int len){
	Matrix ret;
	for(int i=0;i<len;i++)
		for(int j=0;j<len;j++){
			ll tmp=0;
			for(int k=0;k<len;k++)
				tmp+=1ll*x[i][k]*y[k][j];
			ret[i][j]=tmp%mod;
		}
	return ret;
}
Matrix qpow(Matrix x,int n,int len){
	Matrix ret;
	for(int i=0;i<len;i++)
		for(int j=0;j<len;j++)
			ret[i][j]=(i==j);
	while(n){
		if(n&1)
			ret=mul(ret,x,len);
		x=mul(x,x,len);
		n>>=1;
	}
	return ret;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%d",a+i);
	Matrix c;
	c[0][0]=1;c[0][1]=0;c[0][2]=0;c[0][3]=1;
	c[1][0]=2;c[1][1]=1;c[1][2]=0;c[1][3]=2;
	c[2][0]=1;c[2][1]=1;c[2][2]=1;c[2][3]=1;
	c[3][0]=1;c[3][1]=1;c[3][2]=1;c[3][3]=1;
	Matrix dp;
	dp[0][0]=0;dp[0][1]=0;dp[0][2]=0;dp[0][3]=1;
	dp[1][0]=0;dp[1][1]=0;dp[1][2]=0;dp[1][3]=0;
	dp[2][0]=0;dp[2][1]=0;dp[2][2]=0;dp[2][3]=0;
	dp[3][0]=0;dp[3][1]=0;dp[3][2]=0;dp[3][3]=0;
	if(!m){
		dp=mul(dp,qpow(c,n,4),4);
		printf("%d\n",dp[0][3]);
		return 0;
	}
	int lst=0;
	int now=1;
	dp=mul(dp,qpow(c,a[now]-lst-1,4),4);
	lst=a[now]-1;
	while(a[now]+1==a[now+1])
		now++;
	Matrix tmp;
	int l=a[now]+1-lst;
	tmp[0][0]=(1ll*dp[0][3]*l*l+dp[0][0]+1ll*2*l*dp[0][1]+1ll*l*l*dp[0][2])%mod;
	tmp[0][1]=(dp[0][1]+1ll*dp[0][2]*l+1ll*dp[0][3]*l)%mod;
	tmp[0][2]=(dp[0][2]+dp[0][3])%mod;
	tmp[0][3]=tmp[0][0];
	dp[0][0]=tmp[0][0];
	dp[0][1]=tmp[0][1];
	dp[0][2]=tmp[0][2];
	dp[0][3]=tmp[0][3];
	now++;
	c[0][0]=2;c[0][1]=1;c[0][2]=1;
	c[1][0]=2;c[1][1]=1;c[1][2]=0;
	c[2][0]=1;c[2][1]=1;c[2][2]=1;
	while(now<=m){
		dp=mul(dp,qpow(c,a[now]-a[now-1]-2,3),3);
		lst=a[now]-1;
		while(a[now]+1==a[now+1])
			now++;
		Matrix tmp;
		int l=a[now]+1-lst;
		tmp[0][0]=(1ll*dp[0][0]*l*l+dp[0][0]+1ll*2*l*dp[0][1]+1ll*l*l*dp[0][2])%mod;
		tmp[0][1]=(dp[0][1]+1ll*dp[0][2]*l+1ll*dp[0][0]*l)%mod;
		tmp[0][2]=(dp[0][2]+dp[0][0])%mod;
		dp[0][0]=tmp[0][0];
		dp[0][1]=tmp[0][1];
		dp[0][2]=tmp[0][2];
		now++;
	}
	dp=mul(dp,qpow(c,n-a[m]-1,3),3);
	printf("%d\n",dp[0][0]);
	return 0;
}

Measured memory_bytes: 3592
import std.stdio, std.conv, std.string, std.array, std.range, std.algorithm, std.container;
import std.math, std.random, std.bigint, std.datetime, std.format;
void main(string[] args){ if(args.length > 1) if(args[1] == "-debug") DEBUG = 1; solve(); }
void log()(){ writeln(""); } void log(T, A ...)(T t, lazy A a){ if(DEBUG) write(t, " "), log(a); } bool DEBUG = 0; 
string rstring(){ static string[] ss; while(!ss.length) ss = readln.chomp.split; string res = ss[0]; ss.popFront; return res; }
T rtype(T)(){ return rstring.to!T; } alias rint = rtype!int, rlong = rtype!long, rreal = rtype!real;
T[] rtypes(T)(int n){ return n.iota.map!(i => rtype!T()).array; } alias rint = rtypes!int, rlong = rtypes!long, rreal = rtypes!real;
T[][] rtypess(T)(int n, int m){ return n.iota.map!(i => rtypes!T(m)).array; } alias rint = rtypess!int, rlong = rtypess!long, rreal = rtypess!real;

// ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- //

void solve(){
	
	int n = rint;
	string s = rstring;
	
	string ans = "Yes";
	if(n % 2 != 0) ans = "No";
	foreach(i; 0 .. n / 2){
		if(s[i] != s[i + n / 2]) ans = "No";
	}
	
	ans.writeln;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N;
  cin >> N;
  int64_t a = 2;
  int64_t b = 1;
  int64_t c;
  if(N > 1){
     for(int i = 1;i < N; i++){
       c = a + b;
       a = b;
       b = c;
     }
     printf("%ld",c);
  }
  else{
    cout << 1 << 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 bitrep(X,N) for(ll X = 0; X < (1 << (N)); X++)
#define PI (acos(-1.0))
#define sorta(V) sort(V.begin(), V.end())
#define pback push_back
#define mpair make_pair
#define MODN 1000000007
#define ALL(V) (V).begin(),(V).end() 
#define CERR if(false) cerr

using namespace std;


int main(){

    // a % bが k以上,よりbは    　k + 1, k + 2, k + 3,... n
    // a は kからb刻みにnまでの取りうる値を取る

    int n,k;
    cin >> n >> k;

    ll ans = 0;

   
    for(int b = k + 1; b <= n; b++){
        /*
        for(int m = k; m < b; m++){
            if(m != 0){
                ans += (n - m) / b + 1;
            }else{
                ans += (n - m) / b;
            }
        }
        上記のコメントアウトした部分と同値な式をかければよい*/

        int div_b = n / b;
        int mod_b = n % b;

        ans += (b - k) * div_b + max(mod_b - k + 1,0);
    }

    if(k == 0) ans -= n;

    cout << ans << endl;
    return 0; 
}

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


 string s1,s2,sol;
  int l1,l2;
 int dp[3030][3030];

void printlcs(int i,int j)
{
    if(s1[i]=='\0' || s2[j]=='\0')
    {
        cout<<sol<<endl;
        return;
    }
    if(s1[i]==s2[j])
    {
        sol+=s1[i];
        printlcs(i+1,j+1);
    }
    else
    {
        if(dp[i+1][j]>dp[i][j+1])
            printlcs(i+1,j);
        else
            printlcs(i,j+1);
    }
}
int lcs(int i,int j)
{
    if(i>=l1 || j>=l2)
        return 0;

    if(dp[i][j]!=-1)
        return dp[i][j];
    int ans=0;

    if(s1[i]==s2[j])
    {
        ans=1+lcs(i+1,j+1);
       // printf("s---- %c\n",s1[i]);
        //printf(" --- %d--i-- %d --  %d---j--- %d  \n",a[i],i,b[j],j);

    }
    else
    {
        int val1=0,val2=0;

        val1=lcs(i+1,j);

        val2=lcs(i,j+1);

        ans=max(val1,val2);
    }

    dp[i][j]=ans;
    return ans;

}


int main()
{

    getline(cin,s1);
    getline(cin,s2);
memset(dp,-1,sizeof(dp));

    l1=s1.size();
    l2=s2.size();
    //printf(" l1-- %d  l2-- %d\n",l1,l2);
    int r=lcs(0,0);
    printlcs(0,0);

    //printf(" r--- %d\n",r);


}


Measured memory_bytes: 36352
#include<stdio.h>
int main()
{
	int n = 0;
	char s[4];
	// 文字列の入力
	scanf("%s", s);
	// 出力
	for (int i = 0; i < 4; i++) {
		if (s[i] == '+')
			n++;
		else if (s[i] == '-')
			n--;
	}

	printf("%d\n", n);

	return 0;
}


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

int main()
{
    int n, k;
    cin >> n >> k;
    int x = n;
    int arr[n];
    while (x--)
        cin >> arr[n - x - 1];
    int dp[n];

    for(int y= 0; y<min(n, k); y++){
        dp[y] = abs(arr[y] - arr[0]);
    }
    if (n <= k)
    {
        cout << dp[n - 1];
        return 0;
    }

    for (int i = k; i < n; i++)
    {
        int karr[k];
        for (int j = 0; j < k; j++)
        {
            karr[j] = dp[i - 1 - j] + abs(arr[i - 1 - j] - arr[i]);
        }
        int min = *min_element(karr, karr + k);
        dp[i] = min;
    }
    cout << dp[n - 1];
}

Measured memory_bytes: 4412
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <string.h>

using namespace std;

int main() {
  int A[30] = {};
  string s;
  cin >> s;

  for(char ch = 'a'; ch <= 'z'; ch++) {
    for(int i = 0; i < s.size(); i++) {
      if(ch == s[i]) A[ch - 'a']++;
    }
  }
  for(int i = 0; i < 30; i++) {
    if(A[i] > 1) {
      cout << "no" << endl;
      return 0;
    }
  }
  cout << "yes" << endl;
}

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

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
typedef long double ld;

const int INF = 1e9;
const ld EPS = 1e-8;

int main(){
  int N, A, B;
  cin >> N >> A >> B;
  vector<int> t(N);
  REP(i,N) cin >> t[i];

  int res = N;
  REP(i,N) {
    if(t[i] >= A && t[i] < B) res--;
  }
  cout << res << endl;
  return 0;
}



Measured memory_bytes: 256
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列
using namespace std;

typedef long long ll;

//マクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000 //10^12
#define MOD 10000007 //10^9+7
#define MAXR 100000 //10^5:最大のrange(素数列挙などで使用)

std::vector<int> eratosthenes( const int N )
{
    std::vector<bool> is_prime( N + 1 );
    for( int i = 0; i <= N; i++ )
    {
        is_prime[ i ] = true;
    }
    std::vector<int> P;
    for( int i = 2; i <= N; i++ )
    {
        if( is_prime[ i ] )
        {
            for( int j = 2 * i; j <= N; j += i )
            {
                is_prime[ j ] = false;
            }
            P.emplace_back( i );
        }
    }
    return P;
}

int main(void){
    int x;
    cin >> x;
    vector<int> primes = eratosthenes(MAXR*10);
    cout << *lower_bound(ALL(primes), x) << endl;
    return 0;
}

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

int main() {

	string S;int cnt=0;
  cin>>S;
  if(S.at(0)=='o'){cnt++;}
  if (S.at(1)=='o'){cnt++;}
	 if (S.at(2)=='o'){cnt++;}
	cout<<700+cnt*100<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<set>
#include<stack>
#include<queue>
#include<string>
#include<algorithm>//min,max,swap,rand,reverse,sort,lower_bound
#include<functional>
#include<vector>
#include<list>
#include<map>
#include<tuple>
#include<cmath>//abs, sin, cos
#include<bitset>
using namespace std;

int main()
{
	char S;
	int count = 0;
	string S_char;
	cin >> S_char;

	if (S_char.size() == 1)
		1 + 1;
	else
	{
		for (int i = 0; i < S_char.size()-1; i++) {
			if (S_char[i] == '0') {
				if (S_char[i + 1] == '0') {
					S_char[i + 1] = '1';
					count++;
				}
			}
			else if(S_char[i] == '1')  {
				if (S_char[i + 1] == '1') {
					S_char[i + 1] = '0';
					count++;
				}
			}
		}
	}
	cout << count << endl;


	return 0;
}

Measured memory_bytes: 512
<?php
$count = trim(fgets(STDIN));
$input = trim(fgets(STDIN));
$array = explode(' ', $input);

$num = 1;
$max = 10 ** 18;

for($i = 0; $i < $count; $i++){
    if ($array[$i] == 0) {
        $num = 0;
        break;
    }
    $num *= $array[$i];
}

if ($num > $max){
    $num = -1;
}

echo $num;

?>

Measured memory_bytes: 25504
#include<iostream>
#include<iomanip>
#include<string>
#include<algorithm>
#include<vector>
#include<utility>
#include<tuple>
#include<map>
#include<queue>
#include<stack>
#include<deque>
#include<bitset>
#include<math.h>
using namespace std;
using ll = int64_t;
using Graph = vector<vector<int> >;
const ll M = 1000000007;

int main(){
    int n,q;
    cin >> n >> q;
    string s;
    cin >> s;
    
    vector<int> cnt;
    cnt.push_back(0);
    int tmp=0;
    for(int i=1;i<n;i++){
        if(s.at(i-1)=='A' && s.at(i)=='C') {
            tmp++;
            cnt.push_back(tmp);
        }else{
            cnt.push_back(tmp);
        }
    }

    for(int i=0;i<q;i++){
        int r,l;
        cin >> r >> l;

        int ans=cnt.at(l-1)-cnt.at(r-1);
        cout << ans << endl;
    }
}

Measured memory_bytes: 4092
import sys
input=sys.stdin.readline
n=int(input())

a=[None]*n
b=[None]*n
c=[None]*n
for i in range(n):
    a[i],b[i],c[i]=map(int,input().split())

dpa=[a[0]]+[None]*(n-1)
dpb=[b[0]]+[None]*(n-1)
dpc=[c[0]]+[None]*(n-1)

for i in range(1,n):
    dpa[i]=a[i]+max(dpb[i-1],dpc[i-1])
    dpb[i]=b[i]+max(dpa[i-1],dpc[i-1])
    dpc[i]=c[i]+max(dpa[i-1],dpb[i-1])

print(max(dpa[-1],dpb[-1],dpc[-1]))

Measured memory_bytes: 85952
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;

// template {{{  0 
// using {{{ 1
using ll = long long int;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vii = vector<pii>;
using vll = vector<pll>;
// }}} 1
// definition {{{ 1
// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)
#define Scll(x) scanf("%lld", &x)
#define Scll2(x,y) scanf("%lld%lld", &x, &y)
#define Scll3(x,y,z) scanf("%lld%lld%lld", &x, &y, &z)
#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2
// constants {{{ 2
#define EPS (1e-7)
#define INF (2e9)
#define PI (acos(-1))
// }}} 2
// systems {{{ 2
#define Repe(x,y,z) for(ll x = z; x < y; x++)
#define Rep(x,y) Repe(x,y,0)
#define RRepe(x,y,z) for(ll x = y-z-1; x >= 0; x--)
#define RRep(x,y) RRepe(x,y,0)
// }}} 2
// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n")
#define YESNO(a) (a)?printf("YES\n"):printf("NO\n")
// }}} 2
// }}} 1
// input {{{ 1
// }}} 1
// }}} 0

int main() {

    int N,Q;
    Scd2(N,Q);

    int a,b;
    vector<vi> e(N);

    Rep(i,N-1){
        Scd2(a,b);
        e[--a].push_back(--b);
    }

    vi w(N);

    Rep(i,Q){
        Scd2(a,b);
        w[--a]+=b;
    }

    stack<int> s;

    s.push(0);

    while( s.size() ){
        int from = s.top();
        int weight = w[from];
        s.pop();
        for( int to : e[from] ){
            w[to] += weight;
            s.push(to);
        }
    }

    Rep(i,N){
        printf ("%d%c", w[i], i == N-1 ? '\n' : ' ' );
    }

    return 0;
}



Measured memory_bytes: 14080
#include <iostream>

#define Nmax int(1e5 + 5)
using namespace std;

int N,X,Q,K;
int a[Nmax],b[Nmax];

int main()
{
    cin >> N >> K >> Q;
    for(int i = 1; i <= Q; ++i)
    {
        cin >> X;
        a[1]--,a[X]++,a[X+1]--;
    }
    for(int i = 1; i <= N; ++i)
    {
        b[i] = b[i - 1] + a[i];
        if(b[i] + K > 0)
            cout << "Yes\n";
        else cout <<"No\n";
    }
    return 0;
}


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

#define ll          long long
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define hell        1000000007
#define rep(i,a,b)  for(int i=a;i<b;i++)
using namespace std;
int n;
vi st[100005];
void solve(){
    cin>>n;
    int m=2;
    while(m*(m-1)/2<n) m++;
    if(m*(m-1)/2!=n){
        cout<<"No"<<endl;
        return;
    }
    int cnt=1;
    rep(i,1,m+1){
        rep(j,i+1,m+1){
            st[i].pb(cnt);
            st[j].pb(cnt++);
        }
    }
    cout<<"Yes"<<endl;
    cout<<m<<endl;
    rep(i,1,m+1){
        cout<<sz(st[i])<<" ";
        for(auto j:st[i]){
            cout<<j<<" ";
        }
        cout<<endl;
    }
}

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

Measured memory_bytes: 4736
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{

    public static void main(String[] args) throws IOException {
        // write your code here

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        //int n = Integer.parseInt(reader.readLine());
        String s = reader.readLine();
        String[] inp = s.split(" ");

        int n = Integer.parseInt(inp[0]);
        int m = Integer.parseInt(inp[1]);

        int[] arr = new int[m];
        String s1 = reader.readLine();
        String[] inp1 = s1.split(" ");

        long sum=0;
        for (int i = 0; i <inp1.length ; i++) {
            arr[i]=Integer.parseInt(inp1[i]);
            sum+=arr[i];
        }

        if(n-sum>=0)
            System.out.println(n-sum);
        else
            System.out.println(-1);
    }
}


Measured memory_bytes: 34280
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string.h>
#include <set>

using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define all(s) s.begin(), s.end()

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> triple;
typedef double D;

const ll INF = 1e9;
const ll MOD = 1000000007;  // 1e9 + 7

vector< vector<int> > A;
set<P> q; // Match queue

// Check the remaining matches. If match can be made, push it to queue.
void check(int i) {
  if (A[i].size() == 0) { return; }
  int j = A[i].back();
  if (A[j].back() == i) {
    if (i > j) { swap(i, j); }  // Force i < j
    q.insert(P(i, j));
  }
}

int main(int argc, char** argv) {
  int N;
  cin >> N;

  A.assign(N, vector<int>(N-1));
  rep(i, N) {
    rep(j, N-1) {
      cin >> A[i][j];
      --A[i][j];
    }
    reverse(all(A[i]));
  }

  // Push first matches.
  rep(i, N) {
    check(i);
  }

  int day = 0;
  while (q.size() > 0) { // Repeat until match que
    set<P> prevQ;
    prevQ.swap(q); // Set q to prevQ, set empty vector to q.
    for (auto p : prevQ) {
      A[p.first].pop_back(); // pop match
      A[p.second].pop_back(); // pop match
    }
    for (auto p : prevQ) {
      check(p.first);
      check(p.second);
    }

    ++day;
  }

  // Check the remaining of A
  rep(i, N) {
    if (A[i].size() != 0) {
      cout << -1 << endl;
      return 0;
    }
  }

  cout << day << endl;
}


Measured memory_bytes: 4224
#include<stdio.h>
#define MAX_N 150
#define INF 10e8
typedef struct {
	int a;
	int b;
	int w;
} hen;

int par[MAX_N];
int rank[MAX_N];
int n,m;
hen dis[20000];

void init(int n){
	int i;
	for(i=0;i<n;i++){
		par[i] = i;
		rank[i] = 0;
	}
}
int find(int x){
	if(par[x]==x){
		return x;
	}else {
		return par[x] = find(par[x]);
	}
}
void unite(int x,int y){
	x =find(x);
	y =find(y);
	if(x==y){
		return ;
	}
	if(rank[x] < rank[y]){
		par[x] = y;
	}else {
		par[y] = x;
		if(rank[x] == rank[y])rank[x]++;
	}
}
int same(int x,int y){
	return find(x)==find(y);
}
int  judge(hen *a,hen *b){
	return (a->w)-(b->w);
}

int Kruskal(int start){
	int eda=0;
	int i,j,k;
	int max=0;
	int min = dis[start].w;
	init(110);
	for(i=start;i<m;i++){
		hen h = dis[i];
		if(!same(h.a,h.b)){
			eda++;
			unite(h.a,h.b);
			max = h.w;
		}
	}
	
	for(i=1;i<n+1;i++){
	//	printf("%d ",find(i));
		if(!same(1,i)){
			return -1;
		}
	}
	if(eda==n-1){
		return max-min;
	}else {
		return INF;
	}
}
int main(){
	int i,j,k;
	int ans=INF;
	int buf=0;
	while(scanf("%d %d",&n,&m)){
		if(n==0&&m==0){
			break;
		}
		for(i=0;i<m;i++){
			scanf("%d %d %d",&dis[i].a,&dis[i].b,&dis[i].w);
		}
		ans=10e8;
		qsort(dis,m,sizeof(hen),judge);
		for(i=0;i<m;i++){
			buf = Kruskal(i);
			if(buf!=-1&&buf<ans){
				ans =buf;
			}
		}
		if(ans==INF){
			printf("%d\n",-1);
		}else {
			printf("%d\n",ans);
		}
	}
	return 0;
}

Measured memory_bytes: 768
#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <bitset>
#include <set>
#include <unordered_set>
#include <cmath>
#include <complex>
#include <deque>
#include <iterator>
#include <numeric>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <limits>
#include <iomanip>
#include <functional>
#include <cassert>
// #include <atcoder/all>
using namespace std;

using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vvll = V<vll>;
#define ALL(v) v.begin(),v.end()
template < class T > inline bool chmax(T& a, T b) {if (a < b) { a=b; return true; } return false; }
template < class T > inline bool chmin(T& a, T b) {if (a > b) { a=b; return true; } return false; }
#define DEBUG_VLL(vec) for(int sz=0;sz<int(vec.size());sz++) std::cerr<<vec[sz]<<(sz==vec.size()-1?'\n':' ');

const long long MOD = 1000000007;
const long long HIGHINF = (long long)1e18;
const int INF = (int)1e9;

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

    ll ans = 0;
    for (ll i = 1; i <= n; i++) {
        ans += n / i;
        if (n % i == 0) ans--;
    }
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 3644
n,m=gets.split.map(&:to_i)
s=[]
p=0
n.times{s<<gets.split.map(&:to_i)}
s.sort_by{|a|a[0]}.each{|x|x[1]>=m ?(p+=x[0]*m;break):(p+=x[0]*x[1];m-=x[1])}
puts p

Measured memory_bytes: 12664
from collections import defaultdict
from subprocess import Popen, PIPE
from itertools import chain, combinations
import numpy as np


def ext_gcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = ext_gcd(b % a, a)
        return g, x - (b // a) * y, y


# from nagiss-san's AC
def fast_prime_factorization(n):
    # 素因数分解（ロー法）  O(n^(1/4) polylog(n))
    return list(map(int, Popen(["factor", str(n)], stdout=PIPE).communicate()[0].split()[1:]))


def solve(n):
    factorization_acl = fast_prime_factorization(2 * n)
    factorization = defaultdict(int)
    for f in factorization_acl:
        factorization[f] += 1
    # print(factorization)
    factor_list = []
    for k in factorization.keys():
        factor_list.append(k ** factorization[k])

    # trivial answer
    res = 2 * n - 1

    # power set
    for s in chain.from_iterable(combinations(factor_list, r) for r in range(len(factor_list) + 1)):
        p = np.int(np.prod(s))
        q = 2 * n // p
        if p == 1 or q == 1:
            continue
        a, x, y = ext_gcd(p, q)
        if x < 0:
            res = min(res, abs(p * x))
        else:
            res = min(res, abs(q * y))
        # print(p, q, p * x, q * y)
    # print(res)
    return res


def main():
    n = int(input())
    res = solve(n)
    print(res)


def test():
    assert solve(11) == 10
    assert solve(20200920) == 1100144


if __name__ == "__main__":
    test()
    main()


Measured memory_bytes: 27464
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
int main(){
    int n,a[50],cnt=0,f;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=0;i<n;i++){
        if(a[i]!=i+1){
            cnt++;
        }
    }
    if(cnt==0||cnt==2){
        printf("YES\n");
    }
    else{
        printf("NO\n");
    }
}

Measured memory_bytes: 128
/* author   : mpily :-()
title : Competing.cpp
time :Sun Mar 22 15:02:46 2020

*/
#include<bits/stdc++.h>
using namespace std;
bool checkpal(string s){
	int low = 0;
	int high = (int)s.size()-1;
	while(low < high){
		if(s[low] != s[high])return false;
		else{
			low++;high--;
		}
	}
	return true;
}
int main(){
	string s;
	cin>>s;
	int n = (int)s.size();
	if(checkpal(s)){
		string a,b;
		int i = 0;
		for(; i < n/2; i++){
			a.push_back(s[i]);
		}
		i++;
		for(;i< n;++i){
			b.push_back(s[i]);
		}
		if(checkpal(a) && checkpal(b)){
			cout<<"Yes\n";
		}
		else{
			cout<<"No\n";
		}
	}
	else{
		cout<<"No\n";	
	}
	return 0;
}


Measured memory_bytes: 256
import math
N=int(input())
mid=int(math.sqrt(N))
flg=0
for i in range(mid,10**5+1):
    if N%i == 0:
        flg=1
        break
if flg==0:
    for i in range(mid,0,-1):
        if N%i == 0:
            break
dekaiyo=max(N/i,i)
count=1
while dekaiyo>=10:
    dekaiyo/=10
    count+=1
print(str(count))

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

using namespace std;
typedef long long ll;

#define REP(i, n) for(ll i=0;i<(ll)(n);i++)
#define RREP(i, n) for(ll i=(ll)(n-1);i>=0;i--)
#define FOR(i, a, b) for(ll i=(ll)(a), i<=(ll)(b); i++)
#define RFOR(i, a, b) for(ll i=(ll)(a);i>=(ll)(b); i--)
#define ALL(x) (x).begin(),(x).end()
#define SIZE(x) ((ll)(x).size())
#define INF 1000000000000
#define MOD 10000007
#define PB push_back
#define MP make_pair
#define F first
#define S second

signed main()
{
	ll H, N;
	cin >> H >> N;
	REP(i, N){
		ll a;
		cin >> a;
		H-=a;
		if(H<=0){
			cout << "Yes";
			return 0;
		}
	}
	cout << "No" << endl;
}


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

using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1LL << (n))
#define FOR(i, begin, end) for (int i = (begin), i##_end_ = (end); i < i##_end_; i++)
#define IFOR(i, begin, end) for (int i = (end)-1, i##_begin_ = (begin); i >= i##_begin_; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)
#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define eprintf(...) 42
#endif

int main()
{
    lint n;
    cin >> n;
    lint ans, tmp;
    vector<lint> f(n+1);
    lint x;
    REP(i,n){
        if(i*i>n){
            x = i;
            break;
        }
    }
    x++;
    FOR(i, 1, x)
    FOR(j, 1, x)
    FOR(k, 1, x)
    {
        lint nn = i * i + j * j + k * k + i * j + j * k + k * i;
        if(nn<=n)f[nn]++;
    }
    FOR(i,1,n+1){
        cout << f[i] << "\n";
    }

    return 0;
}

Measured memory_bytes: 3652
#ifndef Local
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma comment(linker, "/STACK:1024000000,1024000000")
#endif

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define popCnt(x) (__builtin_popcountll(x))
typedef long long Long;

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#ifdef Local
  freopen("test.in", "r", stdin);
#else
#define endl '\n'
#endif

  Long n;
  cin >> n;

  Long res = 0;

  for (Long i = 1; i * i <= n; ++i) {
    if (n % i != 0) continue;
    Long d = n / i;

    if (i < d - 1) {
      res += d - 1;
    }

  }

  cout << res;

}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <stdio.h>
using namespace std;
const string NO = "no guest";
const int dt[6] = {11,15,18,21,21,26};

int main(){
  vector<string> time(3);
  time[0] = "lunch";
  time[1] = "dinner";
  time[2] = "midnight";
  int n;
  while(cin >> n,n != 0){
    vector<pair<int,int> > per(3,pair<int,int>(0,0));
    for(int i = 0;i < n;i++){
      int h,m,t;
      scanf("%d:%d %d",&h,&m,&t);
      if(h < 2)h+=24;
      if(m > t)t+=60;
      for(int k =0;k < 6;k+=2){
	if(dt[k] <= h &&  h < dt[k+1]){
	  
	  if(t-m <= 8){
	    per[k/2].first++;
	  }
	  per[k/2].second++;
	}
      }
    }
    for(int i = 0;i < 3;i++){
      cout << time[i] << " ";
      if(per[i].second == 0)cout << NO << endl;
      else cout << per[i].first*100/per[i].second << endl;
    }
  }
  
  return 0;
}

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

using namespace std;

#define endl            "\n"
#define sz(x)          (int) (x.size())
#define all(v)          v.begin(), v.end()
#define isOdd(n)       (n&1)
#define pow(n, m)      (ll)powl(n, m)
#define clr(x, val)     memset(x, val, sizeof(x))

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


int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, x, t; cin >> n >> x >> t;
    cout << (n/x + (n % x != 0)) * t;
    return 0;
}



Measured memory_bytes: 3608
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <limits>

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

//math
//-------------------------------------------
template<class T> inline T sqr(T x) { return x * x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define EXISTch(s,c) ((((s).find_first_of(c)) != std::string::npos)? 1 : 0)//cがあれば1 if(1)
#define SORT(c) sort((c).begin(),(c).end())

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18

int main() {
	LL l, r; cin >> l >> r;

	LL ans = INF2;
	for (LL i = l; i < min(r,l+5000); i++) {
		for (LL j = l+1; j < min(r+1,l+5000); j++) {
			LL tmp = (i * j) % 2019;
			ans = min(ans, tmp);
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    count = 0
    ans = False
    for i in range(n):
        a, b = map(int, input().split())
        if a == b:
            count += 1
        else:
            count = 0
        if count == 3:
            ans = True
    
    print("Yes" if ans else "No")
    
    
    
if __name__ == "__main__":
    main()


Measured memory_bytes: 9064
#include "bits/stdc++.h"
#include <unordered_set>

#define _CRT_SECURE_NO_WARNINGS

#define FOR(i, x, n) for(decltype(x) i = (x); i < (n); i++)
#define REP(i, n) for(decltype(n) i = 0; i < (n); i++)
#define RREP(i, n) for (decltype(n) i = (n) - 1; i >= 0; i--)

#define ALL(a) (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define DESCSORT(c) sort(c.begin(), c.end(), greater<int>())

using namespace std;

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

using LL = long long int;
using LD = long double;

const int INF = (1 << 30) - 1;
const LL INF64 = ((LL)1 << 62) - 1;
const double PI = 3.1415926535897932384626433832795;

using pii = pair<int, int>;
using pll = pair<LL, LL>;
using pdd = pair<double, double>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vl = vector<LL>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
using vd = vector<double>;
using vvd = vector<vd>;
using vs = vector<string>;
using vb = vector<bool>;
using vvb = vector<vb>;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int a, b;
	string op;
	cin >> a >> op >> b;

	if (op == "+") {
		cout << a + b << endl;
	} else {
		cout << a - b << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N;
    cin >> N;
    int p[N];
    for (int i = 0; i < N; i++) {
        cin >> p[i];
    }
    int ans = 0;
    for (int i = 0; i < N - 1; i++) {
        if (p[i] == i + 1) {
            ans++;
            swap(p[i], p[i + 1]);
        }
    }
    if (p[N - 1] == N) {
        ans++;
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 3912
def i1str():
    return input()


def istrs(n=None):
    if n is None:
        return input().split()
    a = []
    for _ in range(n):
        a.append(istrs())
    return a


def i1num():
    return int(input())


def inums(n=None):
    if n is None:
        return list(map(int, input().split()))
    a = []
    for _ in range(n):
        a.append(inums())
    return a


def ostrs(l, sp=" "):
    print(sp.join(l))


def onums(l, sp=" "):
    print(sp.join(map(str, l)))


def solve(n, aii):
    dp = [[0 for _ in range(n+1)] for _ in range(n+1)]

    for x in range(1, n+1):
        ai, i = aii[x-1]
        dp[x][0] = dp[x-1][0] + ai * (i-x+1)
        dp[0][x] = dp[0][x-1] + ai * (n-x-i)

    for s in range(1, n+1):
        for x in range(1, s):
            y = s - x
            ai, i = aii[s-1]
            dp[x][y] = max(dp[x-1][y] + ai * (i-x+1),
                           dp[x][y-1] + ai * (n-y-i))

    res = 0
    for x in range(n+1):
        if dp[x][n-x] > res:
            res = dp[x][n-x]
    return res


if __name__ == "__main__":
    n = i1num()
    a = inums()
    aii = sorted([(a[i], i)for i in range(n)], reverse=True)
    print(solve(n, aii))


Measured memory_bytes: 125728
N = int(input())
moneys = [tuple(map(str, input().split())) for _ in range(N)]
rate = 380000

total = 0
for money in moneys:
    x, u = money
    x = float(x)
    if u == 'JPY':
        total += x
    else:
        total += x * rate

print(total)



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

using ll = long long;
using pii = pair<int, int>;

#define     endl               '\n'
#define     fast_io            ios::sync_with_stdio(false); cin.tie(0);
#define     all(x)             begin(x), end(x)
#define     debug(x)           cerr <<"Line "<< __LINE__ <<" : "<< #x " = "<< x <<endl;
 
template<typename T, typename TT>
ostream& operator<<(ostream &os, const pair<T, TT> &t) { return os<<"("<<t.first<<", "<<t.second<<")"; }
template<typename T>
ostream& operator<<(ostream& os, const vector<T> &t) { for(auto& i: t) os<<i<<" "; return os; }





int main(int argc, char** argv) {
    //fast_io
    
    int n;
    cin >> n;
    
    vector<int> x(n+1);
    for(int i = 1; i <= n; ++i) cin >> x[i];
    vector<pii> sorted_x;
    for(int i = 0; i < n; ++i) sorted_x.emplace_back(x[i+1], i+1);
    sort(all(sorted_x));
    //cout << sorted_x << endl;
    
    vector<int> a(n*n + 1);

    for(const auto& item : sorted_x) {
	int i = item.second;
	a[x[i]] = i; // i th occurance of i in x[i]
	int slot = 1;
	for(int j = 1; j < i; ++j) { // [1, i) occurances of i
	    while(slot < x[i] && a[slot]) ++slot;
	    if(slot < x[i]) {
		a[slot] = i;
	    } else {
		cout << "No" << endl;
		exit(0);
	    }
	}
    }
    
    for(int ii = n-1; ii >= 0; --ii) {
	int i = sorted_x[ii].second;
	int slot = n*n;
	for(int j = i + 1; j <= n; ++j) {
	    while(slot > x[i] && a[slot]) --slot;
	    if(slot > x[i]) {
		a[slot] = i;
	    } else {
		cout << "No" << endl;
		exit(0);
	    }
	}
    }
    
    cout << "Yes" << endl;
    for(int i = 1; i <= n * n; ++i) cout << a[i] << " ";
    cout << endl;
    
    
    return 0;
}


Measured memory_bytes: 2176
n=int(input())
l=list(map(int,input().split()))
ans=[[]for i in range(n+1)]
for i in range(n):
    ans[l[i]].append(i+1)

    
c=1
tem=[]
ch=0
while 1:
    if c>n:
        break
    else:
        
        if len(ans[c])==0:
            break
        else:
            flag=0
            for i in ans[c]:
                if i>ch:
                    tem.append(i)
                    ch=i
                    flag=1
                    break
            if not flag:
                break
            else:
                c+=1
                    
                
if len(tem)==0:
    print(-1)
else:
    print(n-len(tem))
                
            

Measured memory_bytes: 107344
#include<stdio.h>
    
int main(){
  int a,b,c,x;
  scanf("%d%d%d",&a,&b,&c);

  for(int i=a;i<=b;i++){
    if(c%i == 0) x++;
  }

  printf("%d\n",x);

  return 0;
}


Measured memory_bytes: 2104
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include<bitset>
#include<math.h>
using namespace std;
#define INF 110000000000
#define MOD 1000000007
typedef long long ll;
typedef pair<int,int> P;

int main(){
  ll K;
  string s;
  cin>>s>>K;

  for(int i=0;i<(int)s.size();i++){
    //cout<<K<<endl;
    if(s[i]=='a') continue;
    if(26-(s[i]-'a')<=K){
      K-=26-(s[i]-'a'); 
      s[i]='a';
    } 
  }
  K%=26;
  s[(int)s.size()-1]=(char)(((s[(int)s.size()-1]-'a')+K)%26+'a');
  cout<<s<<endl;
}


Measured memory_bytes: 512
#pragma comment(linker, "/stack:200000000")

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

#define int long long
#define ull unsigned long long
#define ld long double
#define sz(a) (int)a.size()
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp(a, b) make_pair(a, b)
#define ret(a) return cout<<a,0;

using namespace std;
const int N = 4e3 + 123 , mod = 1e9 + 7;
int n , a[N] ,pr[N], dp[N][N];
bool was[N][N];
int get(int l , int r){
	if(l == r)
		return 0;
	if(l == r - 1)
		return a[l] + a[r];
	if(was[l][r])
		return dp[l][r];
	was[l][r] = 1;
	int cur = 1e18;
	for(int i = l ; i < r ; i++)
		cur = min(cur , get(l , i) + get(i + 1 , r));
	dp[l][r] = cur + pr[r] - pr[l - 1];
	return dp[l][r];
}
main(){
	ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);
	cin >> n ;
	for(int i = 1 ; i <= n ; i++){
		cin >> a[i];
		pr[i] = pr[i - 1] + a[i];
	}
	cout << get(1 , n);
}

Measured memory_bytes: 16256
//Author: Fuadul Hasan(fuadul202@gmail.com)
//BSMRSTU,Gopalganj
#include<bits/stdc++.h>
using namespace std;int tc = 1;
#define happy ios::sync_with_stdio(false);
#define coding  cin.tie(0);
#define mp make_pair
#define ll long long
#define Pi atan(1)*4
#define pb  push_back
#define vpr vector<pr> 
#define pr pair<int, int> 
#define vi std::vector<int>
#define vll std::vector<ll>
#define YES printf("YES\n");
#define NO printf("NO\n");
#define Yes printf("Yes\n");
#define No printf("No\n");
#define all(n) n.begin(),n.end()
#define point(x) setprecision(x)
#define Test printf("Case %d: ",tc++);
#define Unique(c) (c).resize(unique(all(c))-(c).begin())

const int M = 1e9 + 7;
const ll  Inf = (ll)2e18 + 5;
const int N   = 2e5 + 5;

int solve() 
{
	//happy coding
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	int x = c/b;
	if(c%b==0) x--;
	if(x*d<a){
		cout<<"Yes"<<endl;
	}else{
		cout<<"No"<<endl;
	}
	return 0;
}
int main(){
	int test = 1;
	//scanf("%d", &test);
	while (test--)solve();return 0;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string a, b;
  cin >> a >> b;
  
  if ( a[0] == b[2] && a[1] == b[1] && a[2] == b[0]){
    cout << "YES" << endl;
  }
  
  else{
    cout << "NO" << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;
template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}
double l2(P p1, P p2) {
  return sqrt((p1.first - p2.first) * (p1.first - p2.first) + (p1.second - p2.second) * (p1.second - p2.second));
}
double distance(int n, const vector<pair<double, double>> &v) {
  double res = 0;
  for(int i=1;i<n;++i) {
    res += l2(v[i-1], v[i]);
  }
  return res;
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  int n; cin >> n;
  vector<pair<double, double>> v(n);
  for(int i=0;i<n;++i) {
    cin >> v[i].first >> v[i].second;
  }
  double ans = 0;
  int fact = 1;
  for(int i=1;i<=n;++i) {
    fact *= i;
  }
  for(int i=0;i<fact;++i) {
    next_permutation(v.begin(), v.end());
    ans += distance(n, v);
  }
  ans /= fact;
  cout << ans << endl;
}


Measured memory_bytes: 256
import java.io.*;
import java.util.*;

public class Main {
	
	static class Lake {
		public final int top;
		public final int area;
	
		public Lake(int top, int area) {
			this.top  = top;
			this.area = area;
		}
	}

	public static void main(String...args)throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Stack<Integer> downPoints = new Stack<>();
		Stack<Lake> lakes = new Stack<>();
		int totalArea = 0;
		char[] diag = br.readLine().toCharArray();
		
		for(int i = 0; i < diag.length; i++) {
			if(diag[i] == '\\') {
				downPoints.push(i);
			} else if(diag[i] == '/' && downPoints.size() > 0) {
				int downPoint = downPoints.pop();
				int nowArea = i - downPoint;
				totalArea += nowArea;
				while(lakes.size() > 0 && lakes.peek().top > downPoint) {
					nowArea += lakes.pop().area;
				}
				lakes.push(new Lake(downPoint, nowArea));
			}
		}
		System.out.println(totalArea);
		System.out.print(lakes.size());
		Stack<Integer> reverseLakes = new Stack<>();
		while(lakes.size() > 0) {
		    reverseLakes.push(lakes.pop().area);
		}
		while(reverseLakes.size() > 0) {
			System.out.print(" " + reverseLakes.pop());
		}
		System.out.println();
	}
}



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

#define ll long long
#define F first
#define S second
#define ii pair < int , int >
#define ever (;;)

const int N = 100;

int n;
ll a[N],money=1000,stocks;
vector <ll> v;

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);

    bool q = 0;
    int pos = 0;

    for(int i=2;i<=n;i++)
        if( a[i] > a[i-1] )
        {
            pos = i-1;
            break;
        }

    if( !pos )
    {
        printf("1000\n");
        return 0;
    }

    v.push_back(a[pos]);
    q = 1;
    for(int i=pos+1;i<=n;i++)
    {
        if( q )
        {
            if( a[i] < a[i-1] )
            {
                v.push_back(a[i-1]);
                q = 0;
            }
        }
        else
        {
            if( a[i] > a[i-1] )
            {
                v.push_back(a[i-1]);
                q = 1;
            }
        }
    }
    v.push_back(a[n]);

    int sz = (int)(v.size());

    for(int i=0;i<sz;i++)
    {
        if( i%2 == 0 )
        {
            stocks = money/v[i];
            money -= stocks*v[i];
        }
        else
        {
            money += stocks*v[i];
            stocks = 0;
        }
    }

    money += stocks*v.back();

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


Measured memory_bytes: 3812
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define maxn 51
#define maxm 300005
#define ll long long 
using namespace std;

struct arr{ll v,w,c;} a[maxn];
int n,i,j,k,fa[maxn],sz[maxn],D,M;
ll sum[maxn],f[maxm],mx;
int cmp(arr a,arr b){return a.v*b.w>b.v*a.w||a.v*b.w==b.v*a.w&&a.w<b.w;}

int main(){
	scanf("%d%d%d",&n,&M,&D);
	scanf("%lld",&sum[1]),sz[1]=1;
	for(i=2;i<=n;i++) scanf("%lld%d",&sum[i],&fa[i]),sz[i]=1;
	for(i=n;i>=2;i--) sum[fa[i]]+=sum[i],sz[fa[i]]+=sz[i];
	for(i=1;i<=n;i++) a[i].v=sz[i],a[i].w=sum[i],a[i].c=min(D,n);
	memset(f,127,sizeof(f)),f[0]=0; 
	int nows=0;
	for(i=1;i<=n;i++) 
		for(j=1;j<=a[i].c;nows+=a[i].v,j++) 
			for(k=nows;k>=0;k--)
				f[k+a[i].v]=min(f[k+a[i].v],f[k]+a[i].w);
	for(i=1;i<=n;i++) a[i].c=D-a[i].c; a[1].c=2e9;
	sort(a+1,a+1+n,cmp),mx=0;
	for(k=0;k<=nows;k++) if (f[k]<=M){
		int res=M-f[k]; ll ans=0;
		for(i=1;i<=n;i++) {
			ll d=min(res/a[i].w,a[i].c);
			ans+=d*a[i].v,res-=d*a[i].w;
		}
		mx=max(mx,ans+k);
	}
	printf("%lld\n",mx);
}

Measured memory_bytes: 4032
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define DUMP(x)  cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for(ll i = m; i < n; i++)
#define IFOR(i, m, n) for(ll i = n - 1; i >= m; i-- )
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define FOREACH(x,a) for(auto& (x) : (a) )
#define ALL(v) (v).begin(), (v).end()
#define SZ(x) ll(x.size())

string t = "SW";
void check(const string& s, vector<int>& ans, ll N){
  FOR(i,1,N-1){
    if(ans[i] == 0 && s[i]=='o' || ans[i] == 1 && s[i] == 'x'){
      if(ans[(N+i+1)%N] == -1) ans[(N+i+1)%N] = ans[i-1];
      else if(ans[(N+i+1)%N] != ans[i-1]) return;
    }else{
      if(ans[(N+i+1)%N] == -1 )ans[(N+i+1)%N] = !ans[i-1];
      else if(ans[(N+i+1)%N] == ans[i-1]) return;
    }
  }
  bool f = false;
  if(ans[N-1] == 0 && s[N-1] == 'o' && ans[N-2] == ans[0]) f = true;
  if(ans[N-1] == 0 && s[N-1] =='x' && ans[N-2] != ans[0]) f =  true;
  if(ans[N-1] == 1 && s[N-1] == 'o' && ans[N-2] != ans[0]) f =  true;
  if(ans[N-1] == 1 && s[N-1] =='x' && ans[N-2] == ans[0]) f =  true;
  if(!f) return;

  REP(i,N){
    cout << t[ans[i]];
  }
  cout << endl;
  exit(0);
}

int main(){
  ll N; cin >> N;
  string s; cin >> s;
  if(s[0]=='o'){
    REP(i,4){//0番が羊と仮定
      vector<int> ans(N,-1);
      if(i==0){//両隣が羊
        ans[0] = 0;
        ans[N-1] = 0;
        ans[1] = 0;
      }else if(i==1){//両隣が狼
        ans[0] = 0;
        ans[N-1] = 1;
        ans[1] = 1;
      }else if(i==2){//0版が狼と仮定
        ans[0] = 1;
        ans[N-1] = 0;
        ans[1] = 1;
      }else{
        ans[0] = 1;
        ans[N-1] = 1;
        ans[1] = 0;
      }
      check(s,ans,N);
    }
  }else{
    REP(i,4){//0番が狼と仮定
      vector<int> ans(N,-1);
      if(i==0){//両隣が羊
        ans[0] = 1;
        ans[N-1] = 0;
        ans[1] = 0;
      }else if(i==1){//両隣が狼
        ans[0] = 1;
        ans[N-1] = 1;
        ans[1] = 1;
      }else if(i==2){//0版が羊と仮定
        ans[0] = 0;
        ans[N-1] = 0;
        ans[1] = 1;
      }else{
        ans[0] = 0;
        ans[N-1] = 1;
        ans[1] = 0;
      }
      check(s,ans,N);
    }
  }
  cout << -1 << endl;
}



Measured memory_bytes: 1016