akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>

using namespace std;

constexpr int INF = (1 << 30)  - 1;

template<typename T>
bool chmax(T& a, T b){
    if(a < b){
        a = b;
        return true;
    }
    return false;
}

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

    int m, n;
    cin >> m >> n;

    string s, t;
    cin >> s >> t;

    vector< vector< vector< vector<int> > > > dp(3, vector< vector< vector<int> > >(2, vector< vector<int> >(m + 1, vector<int>(n + 1, -INF))));
    dp[0][0][0][0] = 0;

    for(int i = 0 ; i <= m ; ++i){
        for(int j = 0 ; j <= n ; ++j){
            if(i < m){
                chmax(dp[0][0][i + 1][j], dp[0][0][i][j]);
            }
            if(j < n){
                chmax(dp[0][0][i][j + 1], dp[0][0][i][j]);
            }

            if(i < m && s[i] == 'I'){
                chmax(dp[1][1][i + 1][j], dp[0][0][i][j] + 1);
                chmax(dp[1][1][i + 1][j], dp[1][0][i][j] + 1);
            }
            if(j < n && t[j] == 'I'){
                chmax(dp[1][1][i][j + 1], dp[0][0][i][j] + 1);
                chmax(dp[1][1][i][j + 1], dp[1][0][i][j] + 1);
            }

            if(i < m && s[i] == 'O'){
                chmax(dp[1][0][i + 1][j], dp[1][1][i][j] + 1);
            }
            if(j < n && t[j] == 'O'){
                chmax(dp[1][0][i][j + 1], dp[1][1][i][j] + 1);
            }

            chmax(dp[2][1][m][n], dp[0][0][i][j]);
            chmax(dp[2][1][m][n], dp[1][1][i][j]);
        }
    }

    cout << dp[2][1][m][n] << endl;

    cout << flush;

    return 0;
}


Measured memory_bytes: 144420
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(), v.end()
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vec;
typedef vector<vec> mat;
const int MOD = 1e9+7;
const int MAXN = 1e5+5;
vector<int> graph[MAXN];
ll dp[MAXN][2]; // {black, white}
int n;
 
void DFS(int curr, int par)
{
    dp[curr][0] = dp[curr][1] = 1;
 
    for(auto& neighbor : graph[curr])
    {
        if(neighbor == par) continue;
        DFS(neighbor, curr);
        (dp[curr][0] *= dp[neighbor][1]) %= MOD;
        (dp[curr][1] *= (dp[neighbor][0] + dp[neighbor][1]) % MOD) %= MOD;
    }
}
 
int main(){
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL);cout.tie(NULL);
	cin >> n;
    for(int i = 0; i < n-1; ++i)
    {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    DFS(1, 1);
    ll ans = (dp[1][0] + dp[1][1]) % MOD;
    cout << ans << "\n";
    return 0; 
}

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

int main() {
	int N, A, B, C, D, E = 0, F = 0;
	cin >> N >> A >> B >> C >> D;

	if (N%A > 0) {
		E = (N / A + 1)*B;
	}
	else {
		E = (N / A)*B;
	}

	if (N%C > 0) {
		F = (N / C + 1)*D;
	}
	else {
		F = (N / C)*D;
	}

	if (E > F) {
		cout << F << endl;
	}
	else {
		cout << E << endl;
	}

}


Measured memory_bytes: 3104
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;


int main(){
    char a[102],b[102],c[102];
    int n;
    scanf("%d %s %s %s",&n,a,b,c);
    int ans = 0;
    for(int i = 0;i < n;i++){
        if(a[i] == b[i] && b[i] == c[i]){
            ans += 0;
        }else if(a[i] == b[i] || b[i] == c[i] || a[i] == c[i]){
            ans += 1;
        }else{
            ans += 2;
        }
    }
    printf("%d\n",ans);
    return 0;
    
}

Measured memory_bytes: 128
N,M=map(int,input().split())
sc=[]
for i in range(M):
  s,c=map(int,input().split())
  sc.append((s,c))
sc=set(sc)
sc=list(sc)
m=len(sc)
if M==0:
  if N==1:
    print(0)
  else:
    print(10**(N-1))
elif N==1 and sc[0][1]==0:
  print(0)
else:
  flag=0
  for i in range(m):
    if sc[i][0]==1:
      if sc[i][1]==0:
        flag=1
        break
      else:
        flag=2
        break
  for i in range(m-1):
    for j in range(i+1,m):
      if sc[i][0]==sc[j][0]:
        flag=1
        break
  if flag==1:
    print(-1)
  elif flag==2:
    x=0
    for i in range(m):
      x=x+(sc[i][1]*10**(N-sc[i][0]))
    print(x)
  elif flag==0:
    x=10**(N-1)
    for i in range(m):
      x=x+(sc[i][1]*10**(N-sc[i][0]))
    print(x)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define XX first
#define YY second
#define pb emplace_back
#define FOR(i,a,b) for(int (i)=(a);i<(b);++(i))
#define EFOR(i,a,b) for(int (i)=(a);i<=(b);++(i))
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define REP rep
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define all(X) (X).begin(),(X).end()
#define eb emplace_back

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef ll LL;
typedef pii PII;
typedef pll PLL;
const ll MOD=1e9+7;

#define rall(X) (X).rbegin(),(X).rend()
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rreps(X,S,Y) for (int (X) = (Y)-1;(X) >= (S);--(X))
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}

int N;
int M;
int A[114][114];
int vec[114][114];
set<int> unused[214];
using Tup = tuple<int, int, int>;
vector<Tup> eds;
map<int, pii> op[214];

void Invert(int v, int uc, int vc) {
  assert(op[v].count(uc));
  int w = v;
  vector<int> vs(1, w);
  vector<int> as;
  while (op[w].count(uc)) {
    int nw, a;
    tie(nw, a) = op[w][uc];
    vs.eb(nw);
    as.eb(a);
    swap(uc, vc);
    w = nw;
  }

  int m = as.size();
  assert(unused[vs.back()].count(uc));
  assert(!op[vs.back()].count(uc));
  unused[vs.back()].insert(vc);
  op[vs.back()].erase(vc);
  rrep(i, m) {
    int a = as[i];
    int u = vs[i];
    int v = vs[i+1];
    op[u][uc] = pii(v, a);
    op[v][uc] = pii(u, a);
    unused[u].erase(uc);
    unused[v].erase(uc);
    swap(uc, vc);
  }
  assert(op[vs.front()].count(uc) && op[vs.front()].count(vc));
  op[vs.front()].erase(uc);
  unused[vs.front()].insert(uc);
}

signed main(){
  ios_base::sync_with_stdio(false);
  cout<<fixed<<setprecision(0);
  cin >> N >> M;
  rep(i, N) {
    rep(j, M) {
      cin >> A[i][j];
      int r = N+(A[i][j]-1) / M;
      eds.eb(Tup(i, r, A[i][j]));
    }
  }

  rep(i, N) {
    rep(j, M) {
      unused[i].insert(j);
      unused[N+i].insert(j);
    }
  }

  for (Tup &p : eds) {
    int u, v, a;
    tie(u, v, a) = p;
    int uc = *unused[u].begin();
    if (!unused[v].count(uc)) {
      assert(unused[v].size());
      int vc = *unused[v].begin();
      Invert(v, uc, vc);
      assert(unused[u].count(uc));
      assert(unused[v].count(uc));
      assert(op[v].count(vc));
      assert(!unused[v].count(vc));
    }
    unused[u].erase(uc);
    unused[v].erase(uc);
    op[u][uc] = pii(v, a);
    op[v][uc] = pii(u, a);
    continue;
  }

  rep(i, N) {
    rep(j, M) {
      if (j) cout << " ";
      assert(op[i].count(j));
      int a = op[i][j].YY;
      cout << a;
      vec[j][i] = a;
    }
    cout << endl;
  }
  rep(j, M) {
    sort(vec[j], vec[j]+N);
  }
  rep(i, N) {
    rep(j, M) {
      if (j) cout << " ";
      cout << vec[j][i];
    }
    cout << endl;
  }
}


Measured memory_bytes: 1984
#include <bits/stdc++.h>
using namespace std;
int main(){int n,i,r=0;cin>>n;int D,F;for(i=0;i<n;i++){cin>>D>>F;if(D==F)r++;else r=0;if(r==3){cout<<"Yes"<<endl;return 0;}}cout<<"No"<<endl;return 0;}

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

using namespace std;

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

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n)  FOR(i,0,n)
#define INF 1e9

int main(){
    while(true){
        int n,m;
        cin >> n >> m ;
        if(n==0 && m ==0)
            break;
        vector<vector<double>> bt(n,vector<double>(n));
        vector<vector<double>> dp(m,vector<double>(n,0.0));

        FOR(i,0,n){
            FOR(j,0,n){
                cin >> bt[i][j] ;
            }
            dp[0][i] = 1.0;
        }
        double ans = 0;
        FOR(i,0,m-1){
            FOR(j,0,n){
                FOR(k,0,n){
                    dp[i+1][j] = max(dp[i+1][j], dp[i][k] * bt[k][j]);
                }
            }
        }

        FOR(i,0,n)
            ans = max(ans,dp[m-1][i]);

        printf("%.2f\n",ans);
    }
    return 0;
}

Measured memory_bytes: 1356
#include <bits/stdc++.h>
using namespace std;
int main () {
  unsigned long A, C;
  string B;
  cin >> A >> B;
  C = (B.at(0) - '0') * 100 + (B.at(2) - '0') * 10 + (B.at(3) - '0');
  cout << A * C / 100 << endl;
  return 0;
}

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

struct point{int x,y;};

int main(){
    vector<point> p(4);
    for(int i=0;i<2;i++){
        cin >> p[i].x >> p[i].y;
    }
    point v;
    v.x = p[1].x - p[0].x;
    v.y = p[1].y - p[0].y; 

    p[2].x = p[1].x - v.y;
    p[2].y = p[1].y + v.x;

    p[3].x = p[2].x - v.x;
    p[3].y = p[2].y - v.y;
    cout << p[2].x << " " << p[2].y << " " << p[3].x << " " << p[3].y << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define range(i, l, r) for(int (i) = (l); (i) < (r); (i)++)
#define reversed_range(i, l, r) for (int (i) = (r) - 1; (i) >= l; (i)--)
using namespace std;
template <typename T>
using vec = vector<T>;
using lint = long long;
using ulint = unsigned long long;
using pint = pair<int, int>;
using plint = pair<lint, lint>;

template <typename T>
ostream& operator <<(ostream& os, vec<T> v) {
    os << "[";
    for (int i = 0; i < v.size() - 1; i++) {
        os << v.at(i) << ", ";
    }
    return os << v.at(v.size() - 1) << "]";
}


int main() {
    int R, G, B, N;
    cin >> R >> G >> B >> N;
    lint num_combs = 0;
    int possible_num_boxes_R = N / R;
    int possible_num_boxes_G = N / G;
    range(i, 0, possible_num_boxes_R + 1) {
        range(j, 0, possible_num_boxes_G + 1) {
            int num_balls = i * R + j * G;
            int num_rest = N - num_balls;
            if (0 <= num_rest && num_rest % B == 0) {
                // cout << i << " " << j << " " << num_rest / B << "\n";
                num_combs += 1;
            }
        }
    }
    cout << num_combs << "\n";
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define MOD 1000000007
#define MAX(a,b) (a>b?a:b)
#define MAX3(a,b,c) MAX(a,MAX(b,c))
#define MIN(a,b) (a<b?a:b)
#define MIN3(a,b,c) MIN(a, MIN(b,c))
typedef long long lli;
int cmp(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}


int main()
{
    int i, len, red=0, blue=0;
    char s[100000];
    scanf("%s",s);
    len = strlen(s);
    for(i=0; i<len; i++) {
        if(s[i]=='0') {
            red++;
        } else {
            blue++;
        }
    }
    printf("%d",2*MIN(red, blue));
    return 0;
}


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

int main() {
   int n;
   string str_a;
   string str_b;
   string sum = "";

   scanf("%d", &n);
   for(int i=0; i < n; ++i){
       
       cin >> str_a >> str_b;

   int id_a = str_a.size();
   int id_b = str_b.size();
   int c = 0;

   // ???????????????????????°?????????????????????
   while (id_a > 0 || id_b > 0) {
     int a = 0, b = 0;
     // int??§??°???????????????
     if (id_a > 0) a = str_a[--id_a] - '0';
     if (id_b > 0) b = str_b[--id_b] - '0';
     // ?????¨???????????°???????????????c?????????????????????????????°???????????????
     sum = to_string(((a + b + c) % 10)) + sum;
     // ?¬???????????????°????????????????¨????
     c = (a + b + c) / 10;
   }
   if (c > 0) sum = to_string(c) + sum;
       if (str_a.size() > 80 || str_b.size() > 80 || sum.size() > 80){
           cout << "overflow" << endl;}else{
   cout << sum << endl;}
   sum = "";
   }
}

Measured memory_bytes: 3212
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    int a,b,c;
    cin>>a>>b>>c;
    if(a>b)
    {
        if(a-b>=c)
            cout<<0<<endl;
        else cout<<c-a+b<<endl;
    }
    else cout<<c<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
    int main()
    {
        int a,b;
        scanf("%d %d",&a,&b);
        if(a>=2&&a<=13&&b>=2&&b<=13)
        {
              if(a>b)
            printf("Alice");
        else if(b>a)
            printf("Bob");
            else
                printf("Draw");
        }
        else if(a==1&&b==1)
        {
            printf("Draw");
        }
        else if(a==1)
        {
            printf("Alice");
        }
        else if(b==1)
        {
            printf("Bob");
        }

    }



Measured memory_bytes: 128
M = 10**9 + 7

L = input()
L = L[::-1]
len_L = len(L)
ans = 1
count = 0
array_3 = [1]
for _ in range(len(L)):
    array_3.append((array_3[-1] * 3) % M)
for i, c in enumerate(L):
    if c == "1":
        ans *= 2
        ans += array_3[i]
        ans %= M

print(ans)


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


#define rep(i,n) for(int i=0;i<n;++i)

int main(){

  while(1){
    int n,m;
    cin >> n >> m;
    if(n == 0 && m==0)break;
    int h[110],t[110];
    int sumt=0,sumh=0;
    rep(i,n){
      cin >> t[i];
      sumt += t[i];
    }
    rep(i,m){
      cin >> h[i];
      sumh += h[i];
    }
    bool f=false;
    int in,jn,min= 100000007;
    rep(i,n){
      rep(j,m){
	sumt -= t[i];
	sumh -= h[j];
	sumt += h[j];
	sumh += t[i];
	if(sumt == sumh && min > t[i]+h[j]){
	  min =  t[i]+h[j];
	  in = i; jn = j;
	  f = true;
	}
	sumt += t[i];
	sumh += h[j];
	sumt -= h[j];
	sumh -= t[i];
      }
    }
    if(!f) cout << "-1\n";
    else{
      cout << t[in] << " " << h[jn] << endl;
    }
  }
  
  return 0;
}

Measured memory_bytes: 1160
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

vector<int> g[100100];
ll fc[100100]={1ll},nv[100100]={1ll};

ll rwpw(ll a, ll p){
	ll ret = 1ll;
	while(p){
		if(p&1){
			mul_mod(ret,a);
		}
		mul_mod(a,a);
		p >>= 1;
	}
	return ret;
}

int k;

ll solve(int v, int p = -1){
	int i,u,ch=0;
	ll ret = 1ll;
	for(i=(g[v].l_ength()-1); i>=0; --i){
		u = g[v][i];
		if(u==p){
			continue;
		}
		mul_mod(ret,solve(u,v));
		++ch;
	}
	if(p==-1){
		if(k > ch){
			mul_mod(ret,fc[k]);
			mul_mod(ret,nv[k-ch-1]);
		}else{
			ret = 0ll;
		}
	}else{
		if(k-2 < ch){
			ret = 0ll;
		}else{
			mul_mod(ret,fc[k-2]);
			mul_mod(ret,nv[k-2-ch]);
		}
	}
	return ret;
}

int main(void){
	int n,i,a,b;
	cin >> n >> k;
	for(i=1; i<=k; ++i){
		fc[i] = fc[i-1];
		mul_mod(fc[i],i);
		nv[i] = rwpw(fc[i],MOD-2);
	}
	for(i=1; i<n; ++i){
		cin >> a >> b;
		--a; --b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	cout << solve(0) << endl;
	return 0;
}


Measured memory_bytes: 10368
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin>>N;
  int num;
  int card;
long long summ[200020];
  long long sum=0,summin=2e9,ans,sum2;
  for(int i=0;i<N;i++){
    cin>>card;sum+=card;
    summ[i]=sum;
  }
  for(int i=0;i<N-1;i++){
    ans=sum-2*summ[i];
    if(ans<0)
      ans = -(ans);
    summin=min(summin,ans);
  }
  cout<<summin<<endl;
  return 0;
}


Measured memory_bytes: 1792
import java.util.*;

public class Main {

    static int MOD = 1000000007;
    public static void main(String[] args) {


        Scanner sc = new Scanner(System.in);
        long n=sc.nextLong(),m=sc.nextLong();
        long ans=0;
        ans += Math.min(n,m/2);
        n=n-ans;
        m=m-ans*2;
        ans+= m/4;
        System.out.println(ans);

    }

}


Measured memory_bytes: 21588
K, A, B = map(int, input().split())
if A+1>= B:
  ans = K+1
else:
  if K-A-1 < 0:
    n = 0
    ans = K+1
  else:
    n = (K-A-1)//2
    m = (K-A-1)%2
    ans = n*(B-A) + m + B
print(ans)

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

int main() {
  int N;
  cin >> N;
  vector<int>A(N);
  for(int i=0; i<N; i++){
    cin >> A.at(i);
    A.at(i)--;
  }
  
  int count =0;
  
  for(int i=0; i<N; i++){
    int aite = A.at(i);
    if(A.at(aite)==i)count ++;
  }
  
  cout << count/2 <<endl;
}

Measured memory_bytes: 3700
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <climits>
#include <random>
#include <iomanip>

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

typedef long long int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

#define fillInt(xs, x)        \
  for (int i = 0; i < (x); i++) \
    scanf("%d", &xs[i]);
#define fillLong(xs, x)       \
  for (int i = 0; i < (x); i++) \
    scanf("%ld", &xs[i]);
#define fillString(xs, x)       \
  for (int i = 0; i < (x); i++) \
    cin >> xs[i];
#define sortv(xs) sort(xs.begin(), xs.end())
#define sortvinv(xs) sort(xs.begin(), xs.end(), std::greater<long>())
#define lbv(xs, x) lower_bound(xs.begin(), xs.end(), x) - xs.begin()
#define ubv(xs, x) upper_bound(xs.begin(), xs.end(), x) - xs.begin()
#define bs(xs, x) binary_search(xs.begin(), xs.end(), x)
#define index_of(as, x) \
  distance(as.begin(), lower_bound(as.begin(), as.end(), x))

#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define concat(xs, ys) (xs).insert((xs).end(), (ys).begin(), (ys).end())

const int mod = 1000000007;

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

  int n, m;
  cin >> n >> m;
  if (n < 10 && m < 10) {
    cout << n*m << endl;
  } else {
    cout << -1 << endl;
  }

}

Measured memory_bytes: 888
#include <iostream>
#include <cstring>
#define MOD 10000
using namespace std;

int n,k,m[101];
int dp[4][4][4][101];

int rec(int a,int b,int c,int idx){
  if(m[idx] != -1 && m[idx] != c) return 0;
  if(a == b && b == c) return 0;
  if(idx == n) return 1;
  if(dp[a][b][c][idx] != 0) return dp[a][b][c][idx];
  return dp[a][b][c][idx] = (rec(b,c,1,idx+1) + rec(b,c,2,idx+1) + rec(b,c,3,idx+1))%MOD;
}

int main(){
  cin >> n >> k;
  memset(m,-1,sizeof(m));
  while(k--){
    int d,s; cin >> d >> s; 
    m[d] = s;
  }
  cout << (rec(0,0,1,1) + rec(0,0,2,1) + rec(0,0,3,1))%MOD << endl;
}

Measured memory_bytes: 1188
#coding utf-8
N=int(input())
A=[]
for i in range(N):
  A.append(int(input()))

M=max(A)
x=A.index(M)
A[x]=-1
M2=max(A)

for i in range(N):
  if i==x:
    print(M2)
  else:
    print(M)

Measured memory_bytes: 12532
# Union-Findデータ構造
class UnionFind:
    def __init__(self, numV):
        self.pars = list(range(numV))
        self.ranks = [0] * numV
        self.sizes = [1] * numV
    def find(self, x):
        if self.pars[x] == x: return x
        else:
            self.pars[x] = self.find(self.pars[x])
            return self.pars[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        sx, sy = self.sizes[x], self.sizes[y]
        if x == y: return (0, 0)
        if self.ranks[x] < self.ranks[y]:
            self.pars[x] = y
            self.sizes[y] += self.sizes[x]
        else:
            self.pars[y] = x
            self.sizes[x] += self.sizes[y]
            if self.ranks[x] == self.ranks[y]:
                self.ranks[x] += 1
        return (sx, sy)
    def same(self, x, y):
        return self.find(x) == self.find(y)

N, M = map(int, input().split())
ABs = [tuple(map(int, input().split())) for _ in range(M)]

UF = UnionFind(N)

ans = N * (N-1) // 2
anss = [ans]
for i, (A, B) in enumerate(ABs[1:][::-1], 1):
    sx, sy = UF.union(A-1, B-1)
    ans -= sx*(N-sx) + sy*(N-sy) - sx*sy
    ans += (sx+sy) * (N-sx-sy)
    anss.append(ans)

print('\n'.join(map(str, anss[::-1])))


Measured memory_bytes: 35736
#include<stdio.h>

struct test_result{
    signed short ssW_D_mid;
    signed short ssW_D_fin;
    signed short ssW_D_re;
    unsigned char ubW_D_eval;
};

unsigned char evaluate(signed short ssW_D_mid, signed short ssW_D_fin, signed short ssW_D_re);

int main(){
    struct test_result test[50];
    unsigned short usW_C_i;
    unsigned short usW_C_count = 0;

    for(usW_C_i = 0;usW_C_i < 50;usW_C_i++){
        scanf("%d %d %d", &test[usW_C_i].ssW_D_mid, &test[usW_C_i].ssW_D_fin, &test[usW_C_i].ssW_D_re);
        if(test[usW_C_i].ssW_D_mid == -1 && test[usW_C_i].ssW_D_fin == -1 && test[usW_C_i].ssW_D_re == -1){
            break;
        }
        test[usW_C_i].ubW_D_eval = evaluate(test[usW_C_i].ssW_D_mid, test[usW_C_i].ssW_D_fin, test[usW_C_i].ssW_D_re);
        usW_C_count++;
    }

    for(usW_C_i = 0;usW_C_i < usW_C_count;usW_C_i++){
        printf("%c\n", test[usW_C_i].ubW_D_eval);
    }

    return 0;
}

unsigned char evaluate(signed short mid, signed short fin, signed short re){
    signed short ssW_D_sum;
    unsigned char ubW_D_result;

    ssW_D_sum = mid + fin;

    if(mid == -1 || fin == -1){
        ubW_D_result = 'F';
    }
    else if(ssW_D_sum >= 80){
        ubW_D_result = 'A';
    }
    else if(ssW_D_sum >= 65){
        ubW_D_result = 'B';
    }
    else if(ssW_D_sum >= 50){
        ubW_D_result = 'C';
    }
    else if(ssW_D_sum >= 30){
        if(re >= 50){
            ubW_D_result = 'C';
        }
        else{
            ubW_D_result = 'D';
        }
    }
    else{
        ubW_D_result = 'F';
    }

    return ubW_D_result;
}


Measured memory_bytes: 2096
#include <iostream>
#include <algorithm>
#include <array>
#include <cstdint>
#include <functional>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <stdlib.h>
#include <string>
#include <time.h>
#include <utility>
#include <vector>

#define INF 1000000000
#define MOD 1000000007
#define rep(i,a,b) for(uint32 i = (a); i < (b); ++i)
#define bitget(a,b) (((a) >> (b)) & 1)
#define ALL(x) (x).begin(),(x).end()
#define C(x) std::cout << #x << " : " << x << std::endl
#define scanf scanf_s

using int32 = std::int_fast32_t;
using int64 = std::int_fast64_t;
using uint32 = std::uint_fast32_t;
using uint64 = std::uint_fast64_t;



int main(void) {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	uint32 m;
	std::cin >> m;
	std::cout << 24 - m + 24 << "\n";
	return 0;
}

Measured memory_bytes: 256
from collections import defaultdict

def main():
    n, m = map(int, input().split())
    edges = defaultdict(list)

    for _ in range(m):
        a, b = map(int, input().split())
        edges[a].append(b)
        edges[b].append(a)
    
    if solve(n, edges):
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')

def solve(n, edges):
    x = set(edges[1])
    y = set(edges[n])

    if x & y:
        return True
    else:
        return False

main()


Measured memory_bytes: 60172
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ll long long
#define x first
#define y second
#define pii pair<int , int>
#define sz(a) (int)(a.size())
const int INF = 1000 * 1000 * 1000;
const int mod = 998244353;
const int MAX = 1000 * 1000 + 47;
using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);
	int n , k , s;
	cin >> n >> k >> s;
	for(int i = 0; i < k; i++)
		cout << s << " ";
	for(int i = 0; i < n - k; i++)
		cout << (s != INF ? s + 1 : s - 1) << " ";
}


Measured memory_bytes: 1280
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = int(a); i < int(b); ++i)
typedef long long ll;
long long mod = 1e9 + 7;
const long long INF = 1LL << 60;
using namespace std;

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;
}

int main()
{
  string s;
  cin >> s;
  if (s[2] == s[3] && s[4] == s[5])
    cout << "Yes" << endl;
  else
    cout << "No" << endl;

  return 0;
}

Measured memory_bytes: 256
#include<algorithm>
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<stack>
#include<cmath>
#include<list>
#include<set>
#include<map>

using namespace std;
long long MOD = 1000000007LL;
const double PI = 3.14159265358979323846;
#undef INT_MIN
#undef INT_MAX
#define INT_MIN -2147483648
#define INT_MAX 2147483647
#define endl "\n"

int main() {
	int X, N;
	cin >> X >> N;
	map<int, bool> p;
	for (int i = 0; i < N; ++i) {
		int k;
		cin >> k;
		p[k] = true;
	}
	for (int i = 0;; ++i) {
		if (p[X - i] == false) {
			cout << X - i << endl;
			break;
		}
		else if (p[X + i] == false) {
			cout << X + i << endl;
			break;
		}
		else {
			continue;
		}

	}



	return 0;
}

Measured memory_bytes: 3608
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
int main ()
{
	long long sum=0,pan;
	int a[100010];
	int n,t,duan=0,j;
	scanf ("%d",&n);
	t=0;
	for (int i=0;i<n;i++)
	{
		scanf ("%d",&a[i]);
		sum+=a[i];
	}
	sort(a,a+n);
	for (int i=n-1;i>=0;i--)
	{
		if (sum*2<a[n-1])
		{
			pan=sum;
			j=i+1;
			while(j<n)
			{
				
				if (pan*2<a[j])
				{
					duan=1;
					printf ("%d\n",n-i-1);
					break;
				}
				else pan+=a[j];
				if (pan*2>=a[n-1]) 
				{
					break;
				}
				
				j++;
			}
		}
		if (duan==1)
		{
			break;
		}
		sum-=a[i];
	}
	if (duan!=1) printf ("%d",n);
	return 0;
}

Measured memory_bytes: 512
#include <stdio.h>
int main(void){
    int k;
    scanf("%d",&k);
    int su=0;
    for(int i=1;i<=k;i++){
        su=(su*10+7)%k;
        
        if(su%k==0){
            printf("%d\n",i);
            return 0;
        }
    }
    printf("-1\n");
}


Measured memory_bytes: 1736
#include <bits/stdc++.h>
using namespace std;
using pint = pair<int, int>;
using ll = long long;
using pll = pair<ll, ll>;
#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)
#define FI first
#define SE second
#define endl "\n"
#define ciosup cin.tie(0);ios::sync_with_stdio(false);
#define eb emplace_back
constexpr ll INF = 1e9 + 7;
constexpr ll MOD = 1e9 + 7;

int cnte[100'000], cnto[100'000];

int main()
{
    ciosup;
    ll n, cost[5];
    cin >> n;
    REP(i,5)cin >> cost[i];
    ll minc = cost[0];
    ll j = 0;
    ll ans = 0;
    REP(i, 5)
    {
        if (minc >= cost[i]){
            minc = cost[i];
            j = i;
        }
    }
    if (n % minc == 0){
        ans = (n / minc) + 4;
    }else{
        ans = (n / minc + 1) + 4;
    }
    cout << ans << endl;
}

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

long long N, Q;
long long ans[200005];

vector<pair<long long, pair<long long, long long>> >STX;
set<pair<long long, long long>> D;


int main(){
	cin >> N >> Q;
	for(int i = 0; i < N; i++){
		long long s,t,x;
		cin >> s >> t >> x;
		STX.push_back(make_pair(x, make_pair(s,t)));
	}
	for(int i = 0; i < Q; i++){
		long long d;
		cin >> d;
		D.insert(make_pair(d, i));
	}

	sort(STX.begin(), STX.end());
	for(int i = 0; i < N; i++){
		long long left = STX[i].second.first - STX[i].first;
		long long right = STX[i].second.second - STX[i].first;
		long long x = STX[i].first;
		set<pair<long long, long long> >::iterator it = D.lower_bound(make_pair(left, -1));
		while(it != D.end()){
			//cout << "checking " << it->first << ", " << it->second << endl;
			if(it->first >= right){
				break;
			}
			//cout << "removing " << it->first << ", " << it->second << endl;
			ans[it->second] = x;
			D.erase(it++);
		}
	}

	for(long long i = 0; i < Q; i++){
		if(ans[i] == 0){
			cout << -1 << endl;
		}else {
			cout << ans[i] << endl;
		}
	}
}

Measured memory_bytes: 21996
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
/* #pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")*/
typedef long long ll;
const ll MAXN = 1e6 + 2;
const ll MAXK = 1e6 + 2;
const ll MOD = 1e9 + 9;
const ll MODH = 1e9 + 9;
const long double PI = acos(-1);
const ll p = 41;
const long double EPS = 1e-4;
#define x first
#define y second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline ll rand(ll a, ll b) {ll c = rng(); return a+((ll)abs(c))%(b-a+1);}
ll binpow(ll a, ll b, ll m) {a %= m;ll res = 1;while (b > 0) {if (b & 1){res = res * a % m;}a = a * a % m;b >>= 1;
}return res;}


int main(){

ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
string s;
cin >> s;
int r = 0;
int w = 0;
for(int i = 0 ; i < n ; i++){
    r+=(s[i] == 'R');
    w+=(s[i] == 'W');
}
int ans = 0;
for(int i = 0 ; i < r ; i++)
     {
        ans+=(s[i] == 'W');
     }


     cout << ans ;
     

} 

Measured memory_bytes: 3788
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")

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

#define fr                first
#define se                second
#define int               long long
#define pb                push_back
#define mp                make_pair
#define pii               pair<int,int>
#define vi                vector<int>
#define mi                map<int,int>
#define pqb               priority_queue<int>
#define set_bits(x)       __builtin_popcountll(x)
#define mod               1000000007
#define inf               1e18                        //Defining infinity the overflow of int
#define ps(x,y)           fixed<<setprecision(y)<<x   //fir defining the precision int the decimal upto y places. 
#define zrosetbits(x)     __builtin_ctzll(x)         //it will give no of 0's before the first 1 from the right.
#define mk(a,n,type)     type *a=new type[n];
#define test(t)            int t; cin>>t; while(t--)
#define no                cout<<"No\n";
#define yes               cout<<"Yes\n";
#define NO                cout<<"NO\n";
#define YES               cout<<"YES\n";


void io()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin.tie(0);

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}

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


int32_t main()
{

	io();
	clock_t begin = clock();

	int te = 1;


	// test(t)
	//{

	int n;
	cin >> n;

	int a[n] = {0};

	for (int i = 0; i < n; i++)
		cin >> a[i];

	int ans = 0;

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


	cout << ans << "\n";






	//te++;
// double c_time = (double) (clock() - begin) / CLOCKS_PER_SEC;
// cout << ps(c_time, 4) << " seconds\n";
	//}

	return 0;
}





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


int main() {
	
	int N;
	cin >> N;
	bool flag = 0;
	for(int i=0; i<=25; i++){
		for(int j=0; j<=14; j++){
			if(4*i+7*j==N) flag = 1;
		}
	}
	if(flag) cout << "Yes" <<endl;
	else cout << "No" << endl;
	
	return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

typedef long long ll;
typedef uint64_t ull;
typedef pair<int, int> P;
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)

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

    int n;
    cin >> n;
    multiset<int> st;
    for(int i = 0; i < n; ++i){
        int a;
        cin >> a;
        auto it = st.upper_bound(-a);
        if(it == st.end()){
            st.insert(-a);
        }
        else{
            st.erase(it);
            st.insert(-a);
        }
    }
    cout << st.size() << endl;
}

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

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

	map<long long, int> mp;
	for( int i = 0; i < N; i++ ) {
		if( mp[ A[i] ] ) mp[ A[i] ] = 0;
		else mp[ A[i] ] = 1;
	}

	int ans = 0;
	for( auto it = mp.begin(); it != mp.end(); it++ ) {
		if( it->second ) ans++;
	}
	cout << ans << endl;
}


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

int main() {
  int H;
  cin >> H;

  vector<int> dat(H);
  for ( int i = 0; i < H; i++ ) cin >> dat[i];

  for ( int i = 0; i < H; i++ ) {
    printf("node %d: key = %d, ", i+1, dat[i]);
    if ( i ) printf("parent key = %d, ", dat[(i-1)/2]);
    if ( i*2+1 < H ) printf("left key = %d, ", dat[i*2+1]);
    if ( i*2+2 < H ) printf("right key = %d, ", dat[i*2+2]);
    cout << endl;
  }
  
  return 0;
}



Measured memory_bytes: 3232
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cmath>
#include <numeric>

using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)


long long gcm(long long a, long long b)
{
	if (a < b) return gcm(b, a);
	long long r;
	while ((r = a % b)) {
		a = b;
		b = r;
	}
	return b;
}

long long lcm(long long n, long long m)
{
	return n * m / gcm(n, m);
}

int main() {
	long long A, B;
	cin >> A >> B;

	cout << lcm(A, B) << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
typedef long long int ll;
#define mod 1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define m0(x) memset(x,0,sizeof(x))

//qsort用(昇順，降順)
int cmp_asc( const void *p, const void *q ) {
    return *(int*)p - *(int*)q;
}
int cmp_desc( const void *p, const void *q ) {
    return *(int*)q - *(int*)p;
}

//二分累乗法
int powa(ll a, ll n){
	ll res = 1;
	while(n>0) {
		if(n&1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1; 
	}
	return res;
}

//逆元
int inverse(ll a){
	ll n = mod-2;
	return powa(a, n);
}

//組み合わせ（nとrが500以下のとき）
int combination_low(ll n,ll r){
	const ll N = 500;
	ll C[N][N];
	memset(C, 0, sizeof(C));
	C[0][0]=1;
	for(ll n=1; n<N; n++){
		C[n][0]=C[n-1][0];
		for(ll r=1; r<N; r++){
			C[n][r] = C[n-1][r-1] + C[n-1][r];
		}
	}
	return C[n][r];
}

/*組み合わせ*/
int combination(ll n,ll r){
	ll x=1,y=1;
	for(int i=1;i<=r;i++){
		x = x * (n-i+1) % mod;
		y = y * i % mod;
	}
	return x * inverse(y) % mod;
}


int main(void){
	int n,i,c;
	scanf("%d",&n);
	for(i=1;i<10;i++){
		c=i*111;
		if(n<111) break;
		else if(n==c) break;
		else if(n>c && n<c+111){
			c+=111;
			break;
		} 
	}
	printf("%d\n",c);
	return 0;
}

Measured memory_bytes: 128
n = [int(e) for e in input().split(" ")]
a = [int(e) for e in input().split(" ")]
c = 0
s = sum(a) / (4 * n[1])
for e_a in a:
    if s <= e_a:
        c += 1
print("Yes" if n[1] <= c else "No")

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep2(i, m, n) for(int i=int(m); i<int(n); ++i)
#define drep2(i, m, n) for(int i=int(m-1); i>=int(n); --i)
#define rep(i, n) rep2(i, 0, n)
#define drep(i, n) drep2(i, n, 0)
#define all(a) a.begin(), a.end()
#define fst first
#define snd second
using ll = long long;
using ld = long double;
using V = vector<int>;
using Vll = vector<ll>;
using Vld = vector<ld>;
using VV = vector<V>;
using VVll = vector<Vll>;
using VVld = vector<Vld>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
using Pld = pair<ld, ld>;
const int INF = 1<<30;
const ll INFll = 1ll<<62;
const ld EPS = 1e-10;
const int MOD = int(1e9)+7;
template<typename T> inline bool chmin(T& a, T b) {if(a>b) {a=b; return true;} return false;}
template<typename T> inline bool chmax(T& a, T b) {if(a<b) {a=b; return true;} return false;}
template<typename T> inline int Log2(T& x) {int k; for(k=0; (T(1)<<k)<=x; ++k); return k;} // number of binary digits


// initialization
const int F_MAX = int(1e6)+10;
ll fac[F_MAX], finv[F_MAX], inv[F_MAX];
void binom_init() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (int i = 2; i < F_MAX; ++i) {
    fac[i] = fac[i-1] * i % MOD;
    inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
    finv[i] = finv[i-1] * inv[i] % MOD;
  }
}

// binom mod MOD
ll binom(int n, int k) {
  if (k < 0 || n < k) return 0;
  return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD;
}



VV G;


// DP
struct ReRooting {
  // edit area start
  struct DP {
    ll dp;
    int size;
    DP(ll dp=1, int size=0) : dp(dp), size(size) {}
  };
  DP f_merge(DP a, DP b) {
    return DP((a.dp * b.dp) % MOD * binom(a.size + b.size, a.size) % MOD, a.size + b.size);
  }
  DP f_trans(DP a) {
    return DP(a.dp, a.size+1);
  }
  // edit area end

  vector<vector<DP>> dp;
  vector<DP> ans;
  vector<int> p_idx;

  ReRooting(int N) : dp(N), ans(N), p_idx(N) {}

  DP dfs(int u, int p=-1) {
    int d = G[u].size();
    dp[u] = vector<DP>(d);
    DP res;
    rep(i, d) {
      int v = G[u][i];
      if (v == p) {
        p_idx[u] = i;
        continue;
      }
      dp[u][i] = dfs(v, u);
      res = f_merge(res, dp[u][i]);
    }
    return f_trans(res);
  }

  void dfs2(int u, DP pval=DP(), int p=-1) {
    if (p != -1) dp[u][p_idx[u]] = pval;

    int d = G[u].size();
    vector<DP> res_l(d+1), res_r(d+1);
    rep(i, d)  res_l[i+1] = f_merge(res_l[i], dp[u][i]);
    drep(i, d) res_r[i] = f_merge(res_r[i+1], dp[u][i]);

    ans[u] = res_l[d];

    rep(i, d) {
      if (G[u][i] == p) continue;
      dfs2(G[u][i], f_trans(f_merge(res_l[i], res_r[i+1])), u);
    }
  }

  void build() {
    dfs(0);
    dfs2(0);
  }
};


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

  G = VV(N);
  for (int i = 0; i < N-1; ++i) {
    int u, v; cin >> u >> v;
    u--; v--;
    G[u].push_back(v);
    G[v].push_back(u);
  }

  ReRooting reroot(N);
  reroot.build();

  rep(i, N) cout << reroot.ans[i].dp << endl;
  return 0;
}


Measured memory_bytes: 59636
from sys import stdin
import numpy as np

N, K = [int(x) for x in stdin.readline().rstrip().split()]
A = np.sort(np.array([int(x) for x in stdin.readline().rstrip().split()]))
MINUS = A[A<0]
ZERO = A[A==0]
PLUS = A[A>0]

def solve(x):
    count_tpl = 0
    if x >= 0:
        count_tpl += len(ZERO) * N
    count_tpl += np.searchsorted(A, x // PLUS, side='right').sum()
    count_tpl += (N - np.searchsorted(A, (-x-1)//(-MINUS), side='right')).sum()
    count_tpl -= np.count_nonzero(A * A <= x)
    assert count_tpl % 2 == 0
    return count_tpl // 2

left = -10**18
right = 10**18
while left + 1 < right:
    x = (left + right) // 2
    if solve(x) >= K:
        right = x
    else:
        left = x
print(right)

Measured memory_bytes: 32308
using DataStructures
const double = Float64
const int = Int64

parseint(x) = parse(int, x)
readint() = map(parseint, split(readline()))

function main()
  N = readint()[1]
  A = readint()

  MOD = 10^9+7
  S = Vector{int}(undef,N)
  S[N] = A[N]
  for i in N-1:-1:1
    S[i] = (A[i]+S[i+1])%MOD
  end

  s = 0
  for i in 1:N-1
    s = (s + A[i]*S[i+1]) % MOD
  end

  println(s)

end

main()


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

int main()
{
    int n;
    int a, b;
    int min_b, m_a;

    cin >> n;
    cin >> m_a >> min_b;

    for (int i = 1; i < n; i++) {
        cin >> a >> b;

        if (min_b > b) {
            min_b = b;
            m_a = a;
        }
    }

    cout << m_a + min_b << endl;

    return 0;
}


Measured memory_bytes: 256
import java.util.*;
class Main
{
    public static void main (String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[(int)Math.pow(2, n)];
        for(int i = 0; i < a.length; i++) a[i] = sc.nextInt();

        for(int i = 0; i < n; i++){
            for(int j = 0; j < Math.pow(2, n-i); j += 2){
                a[j/2] = Math.abs(a[j] - a[j+1]);
            }
        }
        System.out.println(a[0]);
    }
}

Measured memory_bytes: 92568
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <array>
#include <bitset>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;

int solve(int a, int b, int c){
    vector<int> arr(3);
    int ans = 0;
    arr[0] = a;
    arr[1] = b;
    arr[2] = c;
    sort(arr.begin(), arr.end());
    if(arr[0] % 2 == arr[1] % 2 && arr[1] % 2 == arr[2] % 2){
        ans += (arr[2] - arr[1]) / 2 + (arr[2] - arr[0]) / 2;
    }
    else if(arr[0] % 2 == arr[1] % 2 && arr[0] % 2 != arr[2] % 2){
        ans += (arr[2] - arr[1]) / 2 + (arr[2] - arr[0]) / 2 + 1;
    }
    else {
        ans += (arr[2] - arr[1]) / 2 + (arr[2] - arr[0]) / 2 + 2;
    }
    return ans;
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    int a, b, c;
    cin >> a >> b >> c;
    cout << solve(a, b, c) << endl;
    return 0;
}

Measured memory_bytes: 384
pub fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

pub fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn main() {
    let v = read_vec::<f64>();
    let (a,b,c) = (v[0], v[1], v[2]);
    let c = c * (std::f64::consts::PI / 180.0);
    let h = c.sin() * b;
    let s = a * h / 2.0;
    let q = (a.powf(2.0) + b.powf(2.0) - (2.0 * a * b * c.cos())).sqrt();
    let l = a + b + q;
    println!("{}", s);
    println!("{}", l);
    println!("{}", h);
}



Measured memory_bytes: 5180
#include<stdio.h>
int main(void)
{
	int a, b, i;
	char op;
	
	for (i = 1;i>0;i++)
	{
		scanf("%d %c %d", &a, &op, &b);
		if (op == '+')
		{
			printf("%d\n", a + b);
		}
		
		if (op == '-')
		{
			printf("%d\n", a - b);
		}
		
		if (op == '*')
		{
			printf("%d\n", a*b);
		}
		
		if (op == '/')
		{
			printf("%d\n", a / b);
		}
		
		if (op == '?')
		{
			break;
		}
	}
	return 0;
}


Measured memory_bytes: 2104
#include <iostream>
#include <string>
#include <vector>
#include <cmath>

int main()
{
    int n; std::cin >> n;
    int res = 0;
    std::string s; std::cin >> s;
    std::vector<char> us;

    for (char c : s) {
        if (std::count(us.begin(), us.end(), c) == 0) {
            us.push_back(c);
        }
    }
    // std::cout << "usの出力" << std::endl;
    // for (char c: us) {
    //     std::cout << c << std::endl;
    // }

    for (int i = 1; i <= n; i++) {
        int cnt = 0;
        for (char c : us) {

            // int leftSideCount = std::count(s.begin(), s.begin() + i, c);
            // int rightSideCount = std::count(s.begin() + i, s.end(), c);
            // std::cout << "i:" << i << std::endl;
            // std::cout << "c: " << c << std::endl;
            // std::cout << "leftSideCount: " << leftSideCount << std::endl;
            // std::cout << "rightSideCount: " << rightSideCount << std::endl;
            // std::cout << "* * * *" << std::endl;
            if (std::count(s.begin(), s.begin() + i, c) != 0 && std::count(s.begin() + i, s.end(), c) != 0) {
                cnt++;
            }
            // std::cout << "cnt: " << cnt << std::endl;
        }
        res = std::max(cnt, res);
    }

    std::cout << res << std::endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
// define #Asukaminato is cute
#define ll long long
#define rep(i, m) for (int i = 0; i < (int)(m); i++)
const int inf = 1000000000; // 10^9 Ten to the power of nine.

   int main() {
      int N,M ;
      cin>>N>>M;
      int sum=0;
      int A[10000];

      for (int i = 0; i < M; i++)
      {
         cin>>A[i]; sum+=A[i];
      }
      
      if(N>=sum){cout<<N-sum;}
      else{cout<<-1;}

   }
	

Measured memory_bytes: 3680
#include <stdio.h>

int main(void)
{
    char str[50];
    int i;
	
	char ch[3] = "ABC";
	int c = ch[0];
	scanf("%d",&i);
    scanf("%s", str);
    int count = 0;
    for (i = 0; str[i] != '\0'; i++)
	{
        if (str[i] == ch[0]){
			if (str[i+1] == ch[1]){
				if (str[i+2] == ch[2]){
            		count++;
				}else{}
			}else{}
		}else{}
	}
    printf("%d\n", count);
    
    return (0);
}

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

#define rep(i,n) for(ll i=0;i<(n);++i)
using ll = int_fast64_t;
using pll = pair<ll,ll>;
constexpr ll INF = 1LL<<60;
constexpr ll MOD = 1e9+7;
template<class T> bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T> bool chmin(T &a,const T &b){if(a>b){a=b;return 1;}return 0;}
#if loc||local
void dump(){cerr<<endl;}
template<class T,class... Ts> void dump(T&& h, Ts&&... t){cerr<<h<<", ";dump(forward<Ts>(t)...);}
#else
void dump(){}
template<class T,class... Ts> void dump(T&& h, Ts&&... t){}
#endif
template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;}
template<class T,class U> istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
template<class T> ostream &operator<<(ostream& os,vector<T>const& v){for(auto const& vi:v)os<<vi<<" ";return os;}
template<class T,class U> ostream &operator<<(ostream& os,pair<T,U>const& p){os<<p.first<<","<<p.second;return os;}
template<class T>vector<T> vec(size_t a){return vector<T>(a);}
template<class T, class... Ts>auto vec(size_t a, Ts... ts){return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...));}

signed main(){

  int n;
  cin>>n;
  vector<ll> a(n-1);
  cin>>a;

  vector<int> ans(n);
  for(auto ai:a)ans[ai-1]++;

  for(auto x:ans)cout<<x<<endl;

}

Measured memory_bytes: 5644
x = list(map(int, input().split()))
n = [list(map(int, input().split())) for i in range(2)]
a = sorted(n[0], reverse=True)[0]
b = sorted(n[1])[0]
war = 0
for i in range(x[2]+1, x[3]):
  if (i > a) and (i <= b):
    war = 1
if war == 1:
  print('No War')
else:
  print('War')


Measured memory_bytes: 9180