akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

const int N = 500;
int n , k , col[N][N];
int main(){
	scanf("%d",&k);
	if (k == 1){
		return puts("1\n1") , 0;
	}
	n = ((k + 3) / 4) * 2;
	
	for (int i = 0;i < n;i++)
	for (int j = 0;j < n;j++){
		col[i][j] = (i + j) % n + ( (j & 1) ? n : 0);
		if (col[i][j] >= k) col[i][j] -= n;
	}
	
	
	printf("%d\n",n);
	for (int i = 0;i < n;i++){
		for (int j = 0;j < n;j++){
			printf("%d ",col[i][j]+1);
		}
		putchar('\n');
	}
    return 0;
}

Measured memory_bytes: 2176
import java.util.Scanner;

/**
 * Created by nakatsukatakahiro on 2017/06/10.
 */
class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int r = Integer.parseInt(scanner.next());
        int g = Integer.parseInt(scanner.next());
        int b = Integer.parseInt(scanner.next());

        String rgb =  r + "" + g + "" + b;

        if (Integer.parseInt(rgb) % 4 == 0) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
}


Measured memory_bytes: 22228
#include <iostream>
#include<algorithm>
#include <stdio.h>
#include <map>
#include <random>
#include <string>
#include<vector>
#include<stack>
#include <cstdlib>


using namespace std;

int main() {
	string ans="Yes", n, m, k,t,s;
	cin >> t >> s;
	for (int i = 0; i<t.length(); i++) {
		if (t.at(i) == s.at(i)) {

		}
		else {
			ans = "No";
		}
	}

	
	cout << ans;
	return 0;
}

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

#define F first
#define S second
#define MP make_pair
#define pb push_back
#define all(a) a.begin(), a.end()
#define lcm( a, b ) (a)/__gcd((a),(b))*(b)
#define endl '\n'

using namespace std;

typedef long long LL;
typedef pair< int, int > P;
typedef pair< LL, LL > LP;

static const int INF = INT_MAX;
static const LL LINF = LLONG_MAX;
static const int MIN = INT_MIN;
static const LL LMIN = LLONG_MIN;
static const int MOD = 1000000007;
static const int SIZE = 200005;

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

LL fac[SIZE], finv[SIZE], inv[SIZE];
void combInit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for( int i = 2; i < SIZE; ++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;

    }
}

LL comb(int n, int k) {
    if( n < k ) return 0;
    if( n < 0 || k < 0 ) return 0;
    return (fac[n] * (finv[k] * finv[n - k] % MOD)) % MOD;

}

vector< int > Div( int n ) {
    vector< int > ret;
    for( int i = 1; i * i <= n; ++i ) {
        if( n % i == 0 ) {
            ret.pb( i );

            if( i * i != n ) ret.pb( n / i );
        }
    }
    sort( all( ret ) );
    return ret;
}

void Init();
int Root(int x);
bool Unite(int x, int y);

int root[SIZE];
int sz[SIZE];

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

    int n, m, k;
    cin >> n >> m >> k;
    
    Init();
    int fr[SIZE] = {};
    while( m-- ) {
        int a, b;
        cin >> a >> b;
        Unite(a, b);
        fr[a]++;
        fr[b]++;

    }

    int block[SIZE] = {};
    while( k-- ) {
        int a, b;
        cin >> a >> b;
        if( Root(a) == Root(b) ) {
            block[a]++;
            block[b]++;

        }
    }

    for( int i = 1; i <= n; ++i ) {
        Root(i);
        cout << sz[i] - (block[i] + fr[i] + 1) << " ";

    }
    cout << endl;

    return 0;
}

void Init() {
    for( int i = 0; i < SIZE; ++i ) {
        sz[i] = 1;
        root[i] = i;

    }

    return;
}

int Root(int x) {
    if( x == root[x] ) return x;
    root[x] = Root(root[x]);
    sz[x] = sz[root[x]];
    return root[x];
}

bool Unite(int x, int y) {
    int rx, ry;
    rx = Root(x);
    ry = Root(y);

    if( rx == ry ) return false;
    sz[rx] += sz[ry];
    sz[ry] = sz[rx];
    if( sz[rx] < sz[ry] ) {
        root[rx] = ry;

    } else {
        root[ry] = rx;

    }
    return true;
}


Measured memory_bytes: 4608
#include<iostream>
#include<set>
#include <bitset>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include <cstdio>
#include<algorithm>
#include <sstream>
#include<string>
#include<string.h>
#include <cmath>
#include <iomanip>
#include <string>
#include<list>
#include <limits>
#include <numeric>
#include <type_traits>
#include<bitset>
#define int long long
#define ll long long
#define mod  1000000007
#define inf 1e17
#define rep(i,j,n) for(int i=j;i<n;i++)
#define P pair<int,int>
double pi = 3.141592653589793;
using namespace std;
//ここから始めよう
signed main(){
    int n,k;cin>>n>>k;
    if(k%2==1){
        int h=n/k;cout<<h*h*h<<endl;
    }else {
        int h=n/k;
        int key=2*n/k - h;
        cout<<h*h*h+key*key*key<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
class UnionFind:
    def __init__(self, num):
        self.rank = [0] * num
        self.par = [i for i in range(num)]

    def find_root(self, node):
        if self.par[node] == node:
            return node
        else:
            self.par[node] = self.find_root(self.par[node])
            return self.par[node]

    def same_root(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def union(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        if self.rank[x] > self.rank[y]:
            self.par[y] = x
        else:
            self.par[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1


# Input initial information.
n, m, k = map(int, input().split())
union_find = UnionFind(n)

# Input friend information and union.
direct_friend = [0] * n
for i in range(m):
    a, b = map(int, input().split())
    union_find.union(a - 1, b - 1)
    direct_friend[a - 1] += 1
    direct_friend[b - 1] += 1

# Group connected people.
group = [[] for _ in range(n)]
for i in range(n):
    group[union_find.find_root(i)].append(i)

# Get the count of the group for each (excluding myself).
res = [0] * n
for i in range(n):
    for people in group[i]:
        res[people] = len(group[i]) - 1

# Subtract the number of direct_friend from result.
for i in range(n):
    res[i] -= direct_friend[i]

# Input block information and subtract from result if both are in the same group.
for i in range(k):
    c, d = map(int, input().split())
    if union_find.same_root(c - 1, d - 1):
        res[c - 1] -= 1
        res[d - 1] -= 1

# Print the result.
print(*res)


Measured memory_bytes: 26800
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

class B {
    static void Main(string[] args) {
        int N = int.Parse(Console.ReadLine());
        int[] X = new int[N];
        int[] L = new int[N];

        var list = new List<Tuple<int, int>>();

        for (int i = 0; i < N; i++) {
            var st = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            X[i] = st[0];
            L[i] = st[1];

            list.Add(new Tuple<int, int>(X[i] - L[i], X[i] + L[i]));
        }

        Array.Sort(X);

        int ans = 0;

        list.Sort((a, b) => a.Item2.CompareTo(b.Item2));

        int t = list[0].Item1;  //最後に選んだ機械の右端
        for (int i = 0; i < N; i++) {

            //Console.WriteLine(list[i].Item1);
            //Console.WriteLine(list[i].Item2);

            if (t <= list[i].Item1) {
                ans++;
                t = list[i].Item2;
            }

        }

        Console.WriteLine(ans);

    }
}

Measured memory_bytes: 24116
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();
		int C = sc.nextInt();
		int D = sc.nextInt();
		while (A > 0 && C > 0) {
			C -= B;
			if(C<=0) {
				break;
			}
			A -= D;
		}
		if (A <= 0) {
			System.out.println("No");
		} else {
			System.out.println("Yes");
		}
	}
}

Measured memory_bytes: 35740
#include<bits/stdc++.h>
#define optimize() ios_base ::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl "\n";
using namespace std;


int main()
{
    optimize();
     long long int i,a,b,c,d;
     long long n=-1e18;
     cin>>a>>b>>c>>d;
     n=max({a*c,b*d,a*d,b*c});

     cout<<n;
     cout<<endl;

    return 0;
}



Measured memory_bytes: 3552
#pragma GCC optimize("O3")
#pragma GCC target("sse4")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double PI=acos(-1.0);
#define t1(x)             cerr<<#x<<"="<<x<<endl
#define t2(x, y)          cerr<<#x<<"="<<x<<" "<<#y<<"="<<y<<endl
#define t3(x, y, z)       cerr<<#x<<"=" <<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl
#define t4(a,b,c,d)       cerr<<#a<<"="<<a<<" "<<#b<<"="<<b<<" "<<#c<<"="<<c<<" "<<#d<<"="<<d<<endl
#define t5(a,b,c,d,e)     cerr<<#a<<"="<<a<<" "<<#b<<"="<<b<<" "<<#c<<"="<<c<<" "<<#d<<"="<<d<<" "<<#e<<"="<<e<<endl
#define t6(a,b,c,d,e,f)   cerr<<#a<<"="<<a<<" "<<#b<<"="<<b<<" "<<#c<<"="<<c<<" "<<#d<<"="<<d<<" "<<#e<<"="<<e<<" "<<#f<<"="<<f<<endl
#define GET_MACRO(_1,_2,_3,_4,_5,_6,NAME,...) NAME
#define tr(...) GET_MACRO(__VA_ARGS__,t6,t5, t4, t3, t2, t1)(__VA_ARGS__)
#define __ freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define fastio() ios::sync_with_stdio(0);cin.tie(0)
#define MEMS(x,t) memset(x,t,sizeof(x));
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
/*-------------------------------------------------------------------------------------------------------------------------------------*/
//#define MOD 1000000007
#define endl "\n" 
#define int long long
#define inf 1e18
#define ld long double
/*-------------------------------------------------------------------------------------------------------------------------------------*/
 
int32_t main()
{
	fastio();
	string s,t;
	cin>>s>>t;
	int ans=0;
	for(int i=0;i<s.length();i++)
	{	
		ans+=(s[i]!=t[i]);
	}
	cout<<ans<<endl;
}


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

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

int sum;
int a[20];

bool bit(unsigned int a, int k) {
  return ((a >> (k + 1)) & 1);
}

int diff(int m, int n) {
  return ((m - n > 0) ? m - n : n - m);
}

int pow(int a, int n) {
  int ans = 1;
  REP(i, n) {
    ans *= a;
  }
  return ans;
}

int solve(int n) {
  int repeat = pow(2, n), min = sum;
  for (unsigned int bitset = 0; bitset < repeat; bitset++) {
    int agroup = 0;
    REP(k, n) {
      if (bit(bitset, k))
        agroup += a[k];
    }

    int d = diff(agroup, sum - agroup);
    if (min > d) min = d;
  }

  return min;
}

int main() {
  unsigned int n;
  while (cin >> n and n != 0) {
    sum = 0;
    REP(i, n) {
      cin >> a[i];
      sum += a[i];
    }

    cout << solve(n) << endl;/*
    int k;
    cin >> k;
    cout << bit(n, k) << endl;*/
  }
}

Measured memory_bytes: 1164
#include <algorithm>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define show(x) cout << #x << " = " << (x) << endl;
using namespace std;
using ll = long long;
using pii = pair<int,int>;
ll pre[400][401];
ll dp[400][401];
ll mod = 1e9+7;
ll p[401][401];
ll mod_pow(ll a,ll b){
    if(b==0)return 1;
    if(b==1)return a;
    ll res = mod_pow(a,b/2);
    res = res * res % mod;
    if(b%2)res = res * a % mod;
    return res;
}
int main(){
    int n,c;
    cin >> n >> c;
    vector<int>a(n);
    vector<int>b(n);
    rep(i,n)cin >> a[i];
    rep(i,n)cin >> b[i];
    for(int i = 1; i <= 400; i++){
        p[i][0] = 1;
        for(int k = 1; k <= 400; k++){
            p[i][k] = p[i][k-1] * i % mod;
        }
        for(int k = 0; k <= 400; k++){
            p[i][k] = (p[i][k] + p[i-1][k])%mod;
        }
    }
    dp[0][0] = 1;
    rep(i,n){
        rep(j,c+1){
            rep(k,j+1){
                dp[i+1][j] = (dp[i+1][j] + dp[i][j-k] * (p[b[i]][k]-p[a[i]-1][k]+mod)%mod) % mod;
            }
        }
    }
    cout << dp[n][c] << endl;
}

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

using namespace std;
using ll = long long;

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

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define debug(x) cout << #x << ": " << x << endl;
#define popcnt __builtin_popcount


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

    int res = 0, x = 0;
    for(int i = 0; i < N; i++)
    {
        if(S[i]=='I'){
            x++;
        }else{
            x--;
        }
        res=max(res, x);
    }
    cout<<res<<endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <queue>
#include <list>
#include <stack>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <functional>
#include <iomanip> // std::std::setprecision(X)
#include <limits>  //std::numeric_limits<int>::max(), min()

typedef long long ll;
constexpr long long MOD = 1000000007;
std::string S;
std::vector<std::vector<ll>> dp;

ll sol(ll i, ll j){
  if ( dp[i][j] != -1 ) return dp[i][j];

  ll rtn = 0;
  if ( S[i-1] == '?' ) {
    for(ll k=0; k<13; k++) {
      for(ll l=0; l<10; l++) {
        if ( (10*k+l)%13 == j ) {
          rtn += sol(i-1,k) % MOD;
        }
      }
    }
  }
  else {
    ll s = S[i-1] - '0';
    for(ll k=0; k<13; k++) {
      if ( (10*k+s)%13 == j ) {
        rtn += sol(i-1, k) % MOD;
      }
    }
  }
  return dp[i][j] = rtn % MOD;
}


int main (void) {
  std::cin >> S;
  dp.resize(S.size()+1); for(ll i=0; i<S.size()+1; i++) dp[i].assign(13, -1);

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

  std::cout << sol(S.size(), 5)%MOD << std::endl;
  return 0;
}

Measured memory_bytes: 23040
# include <bits/stdc++.h>
# define rep(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
# define reps(i, n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
# define rrep(i, n) for(int i=((int)(n)-1); i>=0; --i)
# define rreps(i, n) for(int i=((int)(n)); i>0; --i)
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
# define optimize_cin() cin.tie(0); ios::sync_with_stdio(false)
using namespace std;
using ll = long long;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const long long INF = 1LL << 60;

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

uintmax_t combination(unsigned int n, unsigned int r) {
  if ( r * 2 > n ) r = n - r;
  uintmax_t dividend = 1;
  uintmax_t divisor  = 1;
  for ( unsigned int i = 1; i <= r; ++i ) {
    dividend *= (n-i+1);
    divisor  *= i;
  }
  return dividend / divisor;
}

typedef pair<int,int> P;
int main()
{
  int n;
  cin >> n;
  vector<P> p(n);
  rep(i,n) cin >> p[i].second >> p[i].first;
  sort(p.begin(),p.end());
  ll t = 0;
  bool ans = true;

  rep(i,n){
    t+=p[i].second;
    if(t > p[i].first){
      ans = false;
      break;
    }
  } 

  if(ans) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

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

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

    if(N < A){
        cout << "NO" << endl;
    }
    else if(N - A <= B){
        cout << "YES" << endl;
    }
    else{
        cout << "NO" << endl;
    }
}

Measured memory_bytes: 3624
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <climits>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <fstream>

using namespace std;
#define TOSTRING(x) #x
#define SZ(x) (int)(x).size()
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REPR(i,n) for(int i=(n)-1;i>=0;i--)
#define ALL(s) (s).begin(), (s).end()
#define so(V) sort(ALL(V))
#define rev(V) reverse(ALL(V))
#define uni(v) v.erase( unique(ALL(v)) , v.end());
#define PAU system("pause")

typedef long long unsigned int llu;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vb> vvb;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;
const int INF = (1 << 28);
const ll LINF = 1e18;
const double PI = acos(-1);

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, W;
	cin >> N >> W;
	vll dp(100005, LINF);
	dp[0] = 0;
	REP(i, N) {
		int w, v;
		cin >> w >> v;
		vll cur = dp;
		REP(j, 100005) {
			if (j + v > 100002)break;
			cur[j + v] = min(cur[j + v], dp[j] + w);
		}
		dp = cur;
	}
	ll ans = 0;
	REP(i, 100005) {
		if (dp[i] <= W)ans = i;
	}
	cout << ans << endl;
	PAU;
	return 0;
}


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

#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define mp make_pair
#define all(v) v.begin() , v.end()
 
#define rep(i, a, b,r) for (ll i = a, to = b; i < to; i+=r)
#define ren(i, a, b,r) for (ll i = a, to = b; i > to; i-=r)	
 
#define rll(x) ll x;cin>>x;
#define rll2(x,y) ll x,y;cin>>x>>y;
#define rll3(x,y,z) ll x,y,z;cin>>x>>y>>z;
#define rll4(x,y,z,w) ll x,y,z,w;cin>>x>>y>>z>>w;
 
#define rs(s) string s;cin>>s;
 
using namespace std;
 
typedef long long ll;
typedef pair<ll,ll> pll;
const ll MOD=998244353;
 
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<string> vs;
typedef deque<ll> dqll;
 
typedef set<ll> sll;
 
const long double PI = acos(-1);
 
const ll MX=2e5 + 10;
 
const ll MX2=9223372036854775806;
const ll MX3=100000+5;
 

/*PLANTILLA*/
vll vec(10000,0);

 
int main(){
	ios::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
	rll2(x,y);
	ll b=(y-2*x)/2;
	ll a=x-b;
	if((2*a+4*b)==y && a>=0 && b>=0){
		cout<<"Yes\n";
	}else{
		cout<<"No\n";
	}
}

Measured memory_bytes: 3688
import java.lang.Math;
import java.util.ArrayList;
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sn = new Scanner(System.in);
        int i = 1;
        while (sn.hasNext()) {
            int n = sn.nextInt();
            if (n == 0) {
                break;
            }
            System.out.println(String.format("Case %d: %d", i, n));
            i++;
        }
    }
}

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

int main(){
    int n; cin >> n;
    if(n<2){
        cout << 1 << endl;
    }else if(n<4){
        cout << 2 << endl;
    }else if(n<8){
        cout << 4 << endl;
    }else if(n<16){
        cout << 8 << endl;
    }else if(n<32){
        cout << 16 << endl;
    }else if(n<64){
        cout << 32 << endl;
    }else{
        cout << 64 << endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC Optimize("Ofast")

using namespace std;
#define int long long

#define impl(x, last) x == last ? 0 : 63 - __builtin_clz(x ^ last)
struct RadixHeap {
    int last, size_;
    vector<tuple<int, int, bool>> bucket_[64];
    RadixHeap() : last(0), size_(0){}
    void emplace(int x, int val, bool hoge){
        size_++, bucket_[impl(x, last)].emplace_back(x, val, hoge);
    }
    tuple<int, int, bool> pop(bool flag = true){
        if(bucket_[0].empty()){
            int id = 1;
            while(bucket_[id].empty()) id++;
            last = get<0>(*min_element(bucket_[id].begin(), bucket_[id].end()));
            for(auto val : bucket_[id]){
                bucket_[impl(get<0>(val), last)].push_back(val);
            }
            bucket_[id].clear();
        }
        auto res = bucket_[0].back();
        if(flag) size_--, bucket_[0].pop_back();
        return res;
    }
    tuple<int, int, bool> top(){
        return pop(false);
    }
    bool empty(){
        return !size_;
    }
};

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

    int n, m, k;
    cin >> n >> m >> k;
    vector<int> ps(n), cs(n), js(n);
    vector<vector<int>> kidx(k);
    for (int i = 0; i < n; i++) {
        cin >> ps[i];
    }
    for (int i = 0; i < n; i++) {
        int c;
        cin >> c;
        c--;
        cs[i] = c;
        kidx[c].push_back(i);
    }
    for (int i = 0; i < n; i++) {
        cin >> js[i];
    }

    vector<vector<pair<int, int>>> adj(n);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        adj[a].emplace_back(b, c);
        adj[b].emplace_back(a, c);
    }

    vector<vector<int>> dp(n, vector<int>(2, 2e18));
    dp[0][0] = 0;
    dp[0][1] = -ps[0];
//    priority_queue<tuple<int, int, bool>, vector<tuple<int, int, bool>>, greater<>> que;
//    tuple<int, int, bool> : cost, v, bought
    RadixHeap que;

    que.emplace(0, 0, 0);
    que.emplace(-ps[0], 0, 1);

    while (!que.empty()) {
        auto top = que.pop();

        int cost = get<0>(top);
        int v = get<1>(top);
        bool bought = get<2>(top);

        if (cost > dp[v][bought]) continue;
        for (auto &e : adj[v]) {
            int to = e.first, dist = e.second;
            if (bought) {
                if (cost + dist < dp[to][bought]) {
                    dp[to][bought] = cost + dist;
                    que.emplace(dp[to][bought], to, bought);
                }
            } else {
                if (cost + dist < dp[to][bought]) {
                    dp[to][bought] = cost + dist;
                    que.emplace(dp[to][bought], to, bought);
                }
                if (cost + dist - ps[to] < dp[to][1]) {
                    dp[to][1] = cost + dist - ps[to];
                    que.emplace(dp[to][1], to, 1);
                }
            }
        }
    }

    for (int i = 0; i < k; i++) {
        int nin = 2e18;
        for (int v : kidx[i]) {
            if (dp[v][0] + dp[v][1] - js[v] < nin) {
                nin = dp[v][0] + dp[v][1] - js[v];
            }
        }
        cout << -nin << '\n';
    }
}


Measured memory_bytes: 39524
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(x)  x.begin(),x.end()
#define vi vector<int>
#define vll vector<ll>
#define print(x) for(auto it=x.begin();it!=x.end();it++) cout<<*it<<' '; cout<<'\n';
#define debug(a,b,c) cout << a << " " << b << " " << c << endl;
#define in(x,n) for(int e=0;e<n;e++){int y;cin>>y;x.pb(y);}
#define inl(x,n) for(int e=0;e<n;e++){ll y;cin>>y;x.pb(y);}
#define lower(sl)  transform(sl.begin(), sl.end(), sl.begin(), ::tolower); 
#define endl "\n";
#define pi pair<int,int>
#define vpi vector<pair<int,int>>
#define vvi vector<vector<int>>
 

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//code here
    ll a, b, c, d;
    cin >> a>> b>>c>>d;
    cout << (ll)max(a*c, max(a*d, max(b*c, b*d)));
}

Measured memory_bytes: 3668
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new  BufferedReader(new InputStreamReader(System.in));
        try {
            String line = reader.readLine();
            int x = Integer.parseInt(line);
            System.out.println(x*x*x);
        } catch (IOException e){
            System.out.println(e);
        } catch (NumberFormatException e){
            System.out.println("Please Input Integar.");
        }
       
      }
   }


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

int main(){
    int h, w;
    cin >> h >> w;
    vector<vector<string>> mas(h, vector<string>(w));

    int index = 0;
    for(int i = 0; i < h; i++){
        string tmp;
        cin >> tmp;
        for(int j = 0;j < w; j++){
            mas[index][j] = tmp[j];
        }
        index++;
    }

    for(int i = 0; i < h; i++){
         bool flag = true;
        for(int j = 0; j < w; j++){
            if(mas[i][j] == "#"){
                flag = false;
                break;
            }
        }
        if(flag){
            for(int j = 0; j < w; j++){
                mas[i][j] = '+';
            }
        }
    }

    for(int i = 0; i < w; i++){
        bool flag = true;
        for(int j = 0; j < h; j++){
            if(mas[j][i] == "#"){
                flag = false;
                break;
            }
        }
        if(flag){
            for(int j = 0; j < h; j++){
                mas[j][i] = '+';
            }
        }
    }

    for(int i = 0; i < h; i++){
        bool flag = true;
        for(int j = 0; j < w; j++){
            if(mas[i][j] != "+"){
                flag = false;
                cout << mas[i][j];
            }
        }
        if(!flag){
            cout << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 768
#include<stdio.h>

int main(void)
{
    char s[5];
    scanf("%s", s);
    
    for(char c = 0; c < 3; c++)
    {
        if(s[c] == s[c + 1])
        {
            printf("Bad");
            return 0;
        }
   }
   
   printf("Good");
   return 0;
}


Measured memory_bytes: 128
// IOI 2021
 
#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define ends ' '
#define die(x) return cout << x << endl, 0
#define all(v) v.begin(), v.end()
#define sz(x) (int)(x.size())
#define debug(x) cerr << #x << ": " << x << endl
#define debugP(p) cerr << #p << ": {" << p.first << ", " << p.second << '}' << endl
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll INF = 1e9;
const ll MOD = 1e9 + 7;

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

const int N = 3e2 + 5;

int DP[N][N][N];
vector<pii> Q[N];

bool Ok(int r, int g, int b) {
	if ((r == g && r != 0) || (g == b && g != 0) || (b == r && b != 0)) return false;
	int k = max(r, max(g, b));
	for (pii p : Q[k]) {
		int x = (r >= p.first) + (g >= p.first) + (b >= p.first);
		if (x != p.second) return false;
	}
	return true;
}

int main() {

	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n, m, ans = 0; cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int l, r, x; cin >> l >> r >> x;
		Q[r].push_back(make_pair(l, x));
	}
	DP[0][0][0] = 1;
	for (int r = 0; r <= n; r++) for (int g = 0; g <= n; g++) for (int b = 0; b <= n; b++) {
		int k = max(r, max(g, b));
		if (!Ok(r, b, g)) DP[r][g][b] = 0;
		DP[k + 1][g][b] = (DP[k + 1][g][b] + DP[r][g][b]) % MOD;
		DP[r][k + 1][b] = (DP[r][k + 1][b] + DP[r][g][b]) % MOD;
		DP[r][g][k + 1] = (DP[r][g][k + 1] + DP[r][g][b]) % MOD;
		if (k == n) ans = (ans + DP[r][g][b]) % MOD;
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 113320
import sys
from io import StringIO
import unittest

def resolve():
    n, m = map(int, input().split())
    print(int(n*(n-1)/2+m*(m-1)/2))

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """2 1"""
        output = """1"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """4 3"""
        output = """9"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """1 1"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_4(self):
        input = """13 3"""
        output = """81"""
        self.assertIO(input, output)

    def test_入力例_5(self):
        input = """0 3"""
        output = """3"""
        self.assertIO(input, output)


if __name__ == "__main__":
    # unittest.main()
    resolve()


Measured memory_bytes: 5592
#include <bits/stdc++.h>
#define rp1(i,n) for ((i)=1;(i)<=(n);(i)++)
#define rp0(i,n) for ((i)=0;(i)<(n);(i)++)
using namespace std;
int n,m,i,fa[100005];
set<int> s;
int fnd(int x){
	if(fa[x]==x) return x;
	return fa[x]=fnd(fa[x]); 
}
int main(){
	cin>>n>>m;
	rp1(i,n) fa[i]=i;
	rp0(i,m){
		int x,y;cin>>x>>y;
		fa[fnd(x)]=fnd(y);
	}
	rp1(i,n) s.insert(fnd(i));
	cout<<s.size()-1<<endl;
	return 0;
}

Measured memory_bytes: 7800
using System;

public class Program
{
  public static void Main(string[] args)
  {
    while(true){
      string[] read = Console.ReadLine().Split(' ');
      int[] scores = new int[3];
      for(int i = 0;i < 3;i++) scores[i] = int.Parse(read[i]);
      if(scores[0] == -1 && scores[1] == -1 && scores[2] == -1) break;
      char grade = 'N';
      if(scores[0] == -1 || scores[1] == -1) grade = 'F';
      else if(scores[0] + scores[1] >= 80) grade = 'A';
      else if(scores[0] + scores[1] >= 65) grade = 'B';
      else if(scores[0] + scores[1] >= 50) grade = 'C';
      else if(scores[0] + scores[1] >= 30)
      {
        grade = 'D';
        if(scores[2] >= 50) grade = 'C';
      }
      else grade = 'F';
      Console.WriteLine(grade);
    }
  }
}

Measured memory_bytes: 8852
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(s,i, n) for (int i = (int)s; i < (int)(n); i++)
#define pb push_back
typedef long long ll;

int main(){
    int n;
    cin>>n;
    vector<int> p(n);
    vector<int> q(n);
    vector<int> a(n);
    rep(i,n)a[i]=i+1;
    rep(i,n){
        cin>>p[i];
    }
    rep(i,n){
        cin>>q[i];
    }
    int aa=0;
    int bb=0;
    int i=0;
    do {
        if(a==p){
            aa=i;
        }
        if(a==q){
            bb=i;
        }
        i++;

        
    } while( next_permutation(a.begin(), a.end()) );
    cout<<abs(aa-bb)<<endl;  
    return 0;
}

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

int main()
{

	int W, H, x, y, r;

	scanf( "%d %d %d %d %d", &W, &H, &x, &y, &r );

	if( x + r <= W && x - r >= 0 && y + r <= H && y - r >= 0 ) printf( "Yes\n" );
	else printf( "No\n" );

	return 0;

}

Measured memory_bytes: 1012
package main

import "fmt"

func main() {
	var a, b, k int
	fmt.Scan(&a, &b, &k)
	var max int
	if a > b {
		max = a
	} else {
		max = b
	}

	nums := make([]int, 0)
	for i := 1; i <= max; i++ {
		if a%i == 0 && b%i == 0 {
			nums = append(nums, i)
		}
	}
	fmt.Println(nums[len(nums) - k])
}


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

int main() {
    string O, E;
    cin >> O;
    cin >> E;
    for (int i = 0; i < (int)E.size(); i++) {
        cout << O[i] << E[i];
    }
    if ((int)O.size() > (int)E.size()) cout << O[O.size()-1];
    cout << endl;
}

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



int main()
{
  int n;cin>>n;
   double p[n+1],q[n+1];
   for(int i=1;i<n+1;i++){
     cin>>p[i];
     q[i]=1-p[i];
   }
   double dp[n+1][n+1];
   for(int i=0; i<n+1;i++){
     for(int j=0;j<n+1;j++)dp[i][j]=0;
   }dp[0][0]=1;
   for(int i=1;i<n+1;i++){
     dp[i][0]=dp[i-1][0]*q[i];
     for(int j=1;j<n+1;j++){
       dp[i][j]=dp[i-1][j]*q[i]+dp[i-1][j-1]*p[i];
          }
   } double ans=0;
   for(int i=n;i<n+1;i+=2){
     for(int j=i/2+1;j<n+1;j++)ans+=dp[i][j];
   }cout<<setprecision(10)<<ans;
}

Measured memory_bytes: 70656
#include<bits/stdc++.h>
using namespace std;
int main(){
int k,s;
cin >> k >> s;

int cnt = 0;
for(int i = 0; i < k + 1; i++){
    for(int j = 0; j < k + 1;j++){
            int z = s - i - j;
            if(0 <= z && z <= k)
            {
                cnt++;
            }
        
    }
}
cout << cnt << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define ll long long
int main()
{
    string s;
    cin>>s;
    s[3]='8';
    cout<<s;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node *link;

struct node{
    int key;
    link left,right,parent;
};
link head;

void insert(int);
void inorder(link);
void preorder(link);

int main(){
    int m,k;
    char jud[10];
    int i;

    head = NULL;

    scanf("%d",&m);
    for(i=0;i<m;i++){
        scanf("%s",jud);
        if(strcmp(jud,"insert") == 0){
            scanf("%d",&k);
            insert(k);
        }
        else if(strcmp(jud,"print") == 0){
            inorder(head);
            printf("\n");
            preorder(head);
            printf("\n");
        }
    }
    return 0;
}

void insert(int k){
    link x,y,z;
    z = malloc(sizeof(struct node));
    z->key=k;
    z->left=NULL;
    z->right=NULL;
    y=NULL;
    x=head;
    while(x!=NULL){
        y=x;
        if(z->key < x->key) x = x->left;
        else x = x->right;
    }
    z->parent = y;

    if(y==NULL) head = z;
    else if(z->key < y->key) y->left = z;
    else y->right = z;
}

void inorder(link h){
    if(h==NULL) return;
    inorder(h->left);
    printf(" %d",h->key);
    inorder(h->right);
}

void preorder(link h){
    if(h==NULL) return;
    printf(" %d",h->key);
    preorder(h->left);
    preorder(h->right);
}



Measured memory_bytes: 25176
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
using ll = long long;
const ll MOD = 1e9 + 7;
const long long INF = 1LL << 60;

void solve(ll x)
{
    for (ll a = -1000; a <= 1000; a++)
    {
        for (ll b = -1000; b <= 1000; b++)
        {
            if (a * a * a * a * a - b * b * b * b * b == x)
            {
                cout << a << " " << b << endl;
                return;
            }
        }
    }
    return;
}

int main()
{
    ll x;
    cin >> x;
    solve(x);
}

Measured memory_bytes: 3548
#include <stdio.h>
#include <algorithm>
 
using namespace std;
 
int partition(int A[],int p,int r){
    int x = A[r];
    int i = p-1;
    for(int j = p; j < r; j++){
        if(A[j] <= x){
            i++;
            swap(A[i],A[j]);
        }
    }
    swap(A[i+1],A[r]);
    return i+1;
}
 
int main(){
    int n,partition_point;
    scanf("%d",&n);
    int A[n];
    for(int i = 0; i < n; i++) scanf("%d",&A[i]);
 
    partition_point = partition(A,0,n-1);
 
    for(int i = 0; i < n-1; i++){
        if(i == partition_point){
            printf("[%d] ",A[i]);
        }else{
            printf("%d ",A[i]);
        }
    }
    if(partition_point == n-1){
        printf("[%d]\n",A[n-1]);
    }else{
        printf("%d\n",A[n-1]);
    }
}




Measured memory_bytes: 2992
import java.util.*;
public class Main 
{
	public static void main(String arg[])
	{
		Scanner in=new Scanner(System.in);
		for(;;)
		{
			int n=in.nextInt();
			String t=in.nextLine();
			ArrayList<String> AL=new ArrayList<String>();
			if(n==0)
				return;
			for(int i=0;i<n;i++)
			{
				String s[]=in.nextLine().split(" ");
				for(int j=0;j<s.length;j++)
					AL.add(s[j]);
			}
			String se=in.next();
			for(int i=0;i<AL.size();i++)
				if(se.charAt(0)!=AL.get(i).charAt(0))
				{
					AL.remove(i);
					i--;
				}
			if(AL.isEmpty())
			{
				System.out.println("NA");
				continue;
			}
			Collections.sort(AL);
			int count[]=new int[AL.size()];
			for(int i=0;i<AL.size()-1;i++)
			{
				while(i+1<AL.size()&&AL.get(i).equals(AL.get(i+1)))
				{
					count[i]++;
					AL.remove(i);
				}
			}
			ArrayList<Integer> cou=new ArrayList<Integer>();
			for(int i=0;i<count.length;i++)
				cou.add(count[i]);

			ArrayList<String> ANS=new ArrayList<String>();
			while(!AL.isEmpty())
			{
				int m=0;
				for(int j=0;j<cou.size();j++)
				{
					if(cou.get(m)<cou.get(j))
						m=j;
				}
				ANS.add(AL.get(m));
				AL.remove(m);
				cou.remove(m);
			}
			int p=0;
			for(int i=0;i<ANS.size();i++)
			{
				if(p==0)
					System.out.print(ANS.get(i));
				else
					System.out.print(" "+ANS.get(i));
				if(i>3)
					break;
				p=1;
			}
			System.out.println();
		}
	}
}

Measured memory_bytes: 38928
import Foundation
func toTuple<T>(_ args: [T]) -> (T, T, T) { (args[0], args[1], args[2]) }
func readInts() -> [Int] { readLine()!.split(separator: " ").map { Int($0)! } }

let (x, y, z) = toTuple(readInts())
print((x - z) / (y + z))

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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    int a, b, c, d;
    long long mx = -2e18;
    cin >> a >> b >> c >> d;
    mx = max(mx, b *1ll* d);
    mx = max(mx, b *1ll* c);
    mx = max(mx, a *1ll* d);
    mx = max(mx, a *1ll* c);
    cout << mx << endl;
}

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

using namespace std;
using ll = long long;

//container util
#define SORT(c) sort((c).begin(),(c).end())

//repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//print
#define pv(val) cerr << #val << '=' << (val) << endl

const int INF = 1e9;

int main(void){

	int N; cin >> N;

	vector<int> A(N);
	REP(i,N) cin >> A[i];

	vector<int> B = A;

	SORT(B);

	REP(i,N){
		if(B.back() == A[i]) cout << B[N-2] << endl;
		else cout << B.back() << endl;
	}



	return 0;

}


Measured memory_bytes: 3200
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;
LL n;
int x, y;
int main()
{
	scanf("%d %d",&x,&y);
	int flag = 0;
	for(int i = 1;i <= 100000000;i++)
	{
		n = i * x;
		if(n % x == 0 && n % y != 0)
		{
			printf("%d\n",n);
			flag = 1;
			return 0;
		}
	}
	if(flag == 0)
	{
		printf("-1\n");
	}
	return 0;
}

Measured memory_bytes: 384
#include<stdio.h>
#define N 3000

double dp[N][N];//i枚目まで見てj枚表の確立
double coin[N];

int main(void){
	int i;
	int j;
	int n;
	double ans =0;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%lf",&coin[i]);
	}
	dp[0][0]=1.0;
	for(i=0;i<n;i++){
		dp[i+1][0]=dp[i][0]*(1.0-coin[i+1]);
	}
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			dp[i+1][j+1]=dp[i][j]*coin[i+1]+dp[i][j+1]*(1.0-coin[i+1]);
		}
	}
	for(j=(n+1)/2;j<=n;j++){
		ans += dp[n][j];
	}
	printf("%.10lf",ans);

	return 0;
}


Measured memory_bytes: 70528
#include <bits/stdc++.h>
#include <typeinfo>
#include <cxxabi.h>
#ifdef LOCAL
#include "dbgtoki.hpp"
#define DUMP(i) dump((string)TOSTRING(i), demangle(typeid(i).name()), __LINE__ , i) 
#else
#define DUMP(i)
#endif

using namespace std;
#define TOSTRING(x) #x
#define SZ(x) (int)(x).size()
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(s) (s).begin(), (s).end()
#define dis distance
#define so(V) sort(ALL(V))
#define rev(V) reverse(ALL(V))
#define uni(v) v.erase( unique(ALL(v)) , v.end());
#define pub push_back
#define sec second
#define fir first

typedef long long unsigned int llu;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector <int> > vvi;
const int EPS = 1e-9;
const int MOD = 1e9+7;
const int INF = (1 << 30);
const double PI = acos(-1);

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll q,h,s,d,n;
	cin >> q >> h >> s >> d >> n;
	s = min({s,h*2,q*4});
	d = min(s*2,d);
	ll ans = n/2*d + (n%2)*s;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#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 pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define ll long long
 
 
 
using namespace std;
void file(){
	#ifndef ONLINE_JUDGE
    	freopen("tst.txt", "r", stdin);
	#endif
}
int tc;
const int N=1e6+7,M=3e5+5,MOD=1e9+7;

int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	//file();
	
	int a,b,c;

	cin>>a>>b>>c;

	if((a+b+c)>=22)cout<<"bust"<<endl;
	else cout<<"win"<<endl;

}


Measured memory_bytes: 256
import sys


def check(t):
    maxx = max(ud_maxx, r_maxx + t, l_maxx - t)
    minx = min(ud_minx, r_minx + t, l_minx - t)
    maxy = max(lr_maxy, u_maxy + t, d_maxy - t)
    miny = min(lr_miny, u_miny + t, d_miny - t)
    return (maxx - minx) * (maxy - miny)


n = int(input())
lr_maxy, lr_miny, ud_maxx, ud_minx = -1e9, 1e9, -1e9, 1e9
l_maxx, l_minx, r_maxx, r_minx = -1e9, 1e9, -1e9, 1e9
u_maxy, u_miny, d_maxy, d_miny = -1e9, 1e9, -1e9, 1e9
for line in sys.stdin:
    x, y, d = line.rstrip().split()
    x, y = int(x), int(y)
    if d == 'L':
        lr_maxy = max(lr_maxy, y)
        lr_miny = min(lr_miny, y)
        l_maxx = max(l_maxx, x)
        l_minx = min(l_minx, x)
    elif d == 'R':
        lr_maxy = max(lr_maxy, y)
        lr_miny = min(lr_miny, y)
        r_maxx = max(r_maxx, x)
        r_minx = min(r_minx, x)
    elif d == 'U':
        ud_maxx = max(ud_maxx, x)
        ud_minx = min(ud_minx, x)
        u_maxy = max(u_maxy, y)
        u_miny = min(u_miny, y)
    else:
        ud_maxx = max(ud_maxx, x)
        ud_minx = min(ud_minx, x)
        d_maxy = max(d_maxy, y)
        d_miny = min(d_miny, y)

inflections = {0}
inflections.add(max(0, l_maxx - ud_maxx))
inflections.add(max(0, (l_maxx - r_maxx) / 2))
inflections.add(max(0, ud_maxx - r_maxx))
inflections.add(max(0, l_minx - ud_minx))
inflections.add(max(0, (l_minx - r_minx) / 2))
inflections.add(max(0, ud_minx - r_minx))

inflections.add(max(0, d_maxy - lr_maxy))
inflections.add(max(0, (d_maxy - u_maxy) / 2))
inflections.add(max(0, lr_maxy - u_maxy))
inflections.add(max(0, d_miny - lr_miny))
inflections.add(max(0, (d_miny - u_miny) / 2))
inflections.add(max(0, lr_miny - u_miny))

print(min(map(check, inflections)))


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

// p : {0, 1} : {Taro, Jiro}
// find X if both plays optimally

ll dp[3001][3001][2], v[3001];

ll recur(int l, int r, bool p) {
	if(l > r)
		return 0;

	ll &ret = dp[l][r][p];
	if(ret != -1)
		return ret;

	if(p == 0)
		return ret = max(recur(l+1, r, not p) + v[l], recur(l, r-1, not p) + v[r]);
	return ret = min(recur(l+1, r, not p), recur(l, r-1, not p));
}


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

	ll sum = 0;
	for(int i = 0; i < n; ++i) {
		cin >> v[i];
		sum += v[i];
	}

	memset(dp, -1, sizeof dp);
	ll x = recur(0, n-1, 0);
	ll y = sum - x;
	cout << x-y << endl;
	return 0;
}

Measured memory_bytes: 141184
def main():
    N = int(input())
    A = list(map(int, input().split()))
    S = [0] * len(A)
    s = 0
    for i, a in enumerate(A):
        s += a
        S[i] = s 
    l = 0
    b = 2
    m = S[-1]
    for c in range(1, N - 2):
        p, q = S[l], S[c] - S[l]
        while l + 1 < c:
            pn, qn = S[l + 1], S[c] - S[l + 1]
            if abs(pn - qn) >= abs(p - q):
                break
            p, q = pn, qn
            l += 1
        if b <= c:
            b = c + 1
        r, s = S[b] - S[c], S[-1] - S[b]
        while b + 1 < N - 1:
            rn, sn = S[b + 1] - S[c], S[-1] - S[b + 1]
            if abs(rn - sn) >= abs(r - s):
                break
            r, s = rn, sn
            b += 1
        m = min(m, max(p, q, r, s) - min(p, q, r, s))
    return m


print(main())


Measured memory_bytes: 25676
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const long long INF = 1LL << 60;
const int mod = 1e9 + 7;

const int m = 2019;

int main()
{
    string s;
    cin >> s;
    int n = s.size();
    reverse(s.begin(), s.end());
    int x = 1, tot = 0;
    vector<int> cnt(m); //累積和のあまりがmになるものの数を保存してる
    ll ans = 0;
    for (int i = 0; i < n; i++)
    {
        cnt[tot]++;
        tot += (s[i] - '0') * x; //一桁ずつ数字をとり、桁数分10倍して足してる
        tot %= m;                //累積和のあまりをとってる
        ans += cnt[tot];
        x = x * 10 % m;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3764
def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    MOD = 10**9+7
    total = sum(A)%MOD
    ans = 0
    for i in range(N):
        total -= A[i]
        total %= MOD
        ans += A[i]*total
        ans %= MOD
    print(ans)
    


if '__main__' == __name__:
    resolve()

Measured memory_bytes: 94356
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
using namespace std;
typedef long long LL;
const int inf = 1 << 30;
const int Inf = 1LL << 60;
const int Maxn = 1e5 + 5;

int main ()
{
	map<int,int>a;
	int n;
	scanf("%d",&n);
	int ans = 0;
	for (int i = 1; i <= n; i++)
	{
		int w;
		scanf("%d",&w);
		if (a[w] == 1){
			a[w] = 0;
			ans--;
		}
		else if (a[w] == 0)
		{
			a[w] = 1; 
			ans++;
		}
	}
	printf("%d",ans);
}

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

int main(){
	int n,k;
	cin >> n>>k;
	std::vector<int> p(n);
	rep(i,n) cin >> p[i];

	sort(p.begin(), p.end());
	int ans = 0;
	rep(i,k) ans += p[i];
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 3600
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int prize = 0;
        int x = sc.nextInt();
        int y = sc.nextInt();
        
        prize += calcPrize(x);
        prize += calcPrize(y);
        if (x == 1 && y == 1) {
            prize += 400000;
        }
        
        System.out.println(prize);
    }
    
    static int calcPrize(int x) {
        switch (x) {
            case 1: return 300000;
            case 2: return 200000;
            case 3: return 100000;
            default: return 0;
        }
    }
}


Measured memory_bytes: 23636
#include <iostream>
#include <math.h>
#include <vector>

using namespace std;

int n, m, qn;
long long m_score = 0;
vector<int> a, b, c, d, seq;

void dfs(vector<int> &seq){
    if (seq.size() == n){
        long long score = 0;
        for (int i=0; i<qn; i++){
            if (seq[b[i]-1]-seq[a[i]-1] == c[i]) score += d[i]; 
        }
        m_score = max(m_score, score);
        return; 
    }

    int l;
    if (seq.size()==0) {
        l = 1;
    }  else {
        l = seq[seq.size()-1];
    }

    for (int i=l; i<=m; i++){
        seq.push_back(i);
        dfs(seq);
        seq.pop_back();
    }
    return;
}

int main(){
    cin >> n >> m >> qn;
    a.resize(qn);
    b.resize(qn);
    c.resize(qn);
    d.resize(qn);

    for (int i=0; i<qn; i++){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    }

    dfs(seq);
    cout << m_score << endl;

    return 0;
}

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

const int N=2e5+20;

int n,k,x;
map <int,queue <int>> m;
long long s,ans;

int main()
{
	scanf("%d%d",&n,&k);
	m[0].push(0);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&x);
		s+=x;

		int r=(s-i)%k;
		m[r].push(i);

		while(i-m[r].front()>=k) m[r].pop();
		ans+=m[r].size()-1;
	}
	printf("%lld",ans);
}

Measured memory_bytes: 147508
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char) 
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    pub fn pair(k: u32) -> u32 {
        let kisu_count = k / 2 + k % 2;
        let gusu_count = k / 2;
        kisu_count * gusu_count
    }

	let k: u32 = read();
    let ans = pair(k);
    println!("{}", ans);
}

Measured memory_bytes: 4352
#include <cstdio>

int main(int argc, char const *argv[]) {
  int N;
  scanf("%d", &N);
  for (int i = 0; i < N; i ++) {
    char c;
    scanf("%c", &c);
    if (c == 'Y') {
      printf("Four\n");
      return 0;
    }
  }
  printf("Three\n");
  return 0;
}


Measured memory_bytes: 128