akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <stack>
#include <cstdlib>
using namespace std;

vector<string> split(const string &str, char delim){
	vector<string> res;
	size_t current = 0, found;
	while((found = str.find_first_of(delim, current)) != string::npos){
		res.push_back(string(str, current, found - current));
		current = found + 1;
	}
	res.push_back(string(str, current, str.size() - current));
	return res;
}

int main(){
	string s;
	stack<double> ans;
	vector<string> strings;
	double a,b;
	while (getline(cin, s)) {
		strings = split(s, ' ');
		for (int i = 0; i < strings.size(); i++) {
			if(strings[i] == "+"){
				a = ans.top();
				ans.pop();
				b = ans.top();
				ans.pop();
				ans.push(b+a);
			}else if (strings[i] == "-") {
				a = ans.top();
				ans.pop();
				b = ans.top();
				ans.pop();
				ans.push(b-a);
			}else if (strings[i] == "*") {
				a = ans.top();
				ans.pop();
				b = ans.top();
				ans.pop();
				ans.push(b*a);
			}else if (strings[i] == "/") {
				a = ans.top();
				ans.pop();
				b = ans.top();
				ans.pop();
				ans.push(b/a);
			}else{
				ans.push(atof(strings[i].c_str()));
			}
		}
		cout << fixed << setprecision(20) << ans.top() << endl;
		ans.pop();
	}
	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#define rep(i,n) Rep(i,0,n)
#define Rep(i,k,n) for(int i=k ; i<n ; i++)
#define rep1(i,n) for(int i=1 ; i<=n ; i++)
#define vi vector<int>
#define vii vector<int,int>
#define Sort(v) sort(v.begin(),v.end())
#define Reverse(v) reverse(v.begin(),v.end())

//const int MOD = 1000000007;
//const int INF = 1<<30;
using namespace std;

string disp(bool x){
    return x ? "Yes" : "No";
}

int main(){
    int x; cin >> x;
    int a[x],b[x];
    rep(i,x) cin >> a[i];
    rep(i,x) cin >> b[i];
    
    int ans = 0;
    rep(k,x){
        int res = 0;
        rep(i,x){
            
            if(i<k) res += a[i];
            if(i>k) res += b[i];
            if(i == k) res = res+a[i]+b[i];
            
        }
        
        ans = max(ans,res);
    }
    
    cout << ans << endl;
}
    
    






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

using namespace std;

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

    int n, r;
    cin >> n >> r;

    vector<int> as(n);
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        a--;
        as[i] = a;
    }

    vector<vector<int>> ps;
    vector<int> sz;
    vector<bool> visited(n);
    for (int i = 0; i < n; i++) {
        if (visited[i]) continue;
        visited[i] = true;
        int idx = i;
        vector<int> idxs = {idx};
        while (1) {
            idx = as[idx];
            if (visited[idx]) break;
            idxs.push_back(idx);
            visited[idx] = true;
        }
        ps.push_back(idxs);
        sz.push_back(idxs.size());
    }

    sort(sz.begin(), sz.end());
    bitset<151515> can_make;
    can_make[0] = 1;
    int MAKE = min(r, n - r);
    for (int a : sz) {
        if (a > MAKE) continue;
        can_make |= can_make << a;
    }
    cout << (can_make[MAKE] ? "Yes" : "No") << endl;
}


Measured memory_bytes: 25408
# include <bits/stdc++.h>
using namespace std;
int main(){
	int n;
  cin >> n;
  int arr[n];
  // storing in array
  for(int i = 0; i < n; i++){
  	cin >> arr[i];
  }
  // summing up
  int res = 0;
  for(int i = 0; i < n; i++){
  	for (int j = 0; j < i; j++){
    	res += arr[i]*arr[j];
    }
  }
  // printing the output
  cout << res <<'\n';
  return 0;
}

Measured memory_bytes: 256
/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
         fozubaoyou    pass System Test!
*/


//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

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

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

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

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define 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)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;


int vector_finder(std::vector<int> vec, int number) {
  auto itr = std::find(vec.begin(), vec.end(), number);
  size_t index = std::distance( vec.begin(), itr );
  if (index != vec.size()) { // 発見できたとき
    return 1;
  }
  else { // 発見できなかったとき
    return 0;
  }
}


int main(){
    double a,b,h,m;
    cin >> a >> b >> h >> m;

    static const double pi = 3.141592653589793;
    double hh = 30 * h + 0.5 * m;
    double mm = 6 * m;
    double theta = (abs(hh-mm) * pi) / 180;
    double c = cos(theta);

    double ans = sqrt(pow(a,2) + pow(b,2) - 2*a*b*c);
    cout << fixed << setprecision(15) << ans << endl;
    return 0;
}


Measured memory_bytes: 4224
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define all(v) (v).begin(),v.end()
set<string> c;
const ll mod=1000000007;
const ll mod2=998244353;
const ll inf=100000000000000000;
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
ll lcm(ll c,ll d){return c/gcd(c,d)*d;}
vector<int> dy={-1,0,1,0},dx={0,-1,0,1};
vector<bool> prime;
int main(){
    int num=55655;
    int sqt_num=(int)sqrt((double)num);
    prime.resize(num,true);
    prime.at(0)=false;
    for(int i=0;i<sqt_num;i++){
        if(prime.at(i)){
            for(int j=2;(i+1)*j<=num;j++){
                prime.at((i+1)*j-1)=false;
            }
        }
    }
int n;
cin>>n;
vector<int>ans;
for(int i=55555;i>=2;i--){
    if(i%5==1&&prime[i-1]){cout<<i<<" ";n--;}
    if(n==0){cout<<endl;return 0;}
}

}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
#define initdp(a, b)  for (int i = 0; i <= a; i++)   for (int j = 0; j <= b; j++) dp[i][j] = -1;
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define ll long long
#define pll pair<ll, ll>
#define all(arr) arr.begin(), arr.end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repd(i, n) for (int i = n - 1; i >= 0; i--)
#define fo(i, l, r) for (int i = l; i <= r; i++)
#define inf 1000000001
#define inf1 1000000000000000001
#define mod 1000000007
#define pie 3.14159265358979323846
#define N 1000005
#define mid(l, r) l + (r - l) / 2
#define vec vector<int>
#define vecl vector<ll>
#define yes cout << "Yes" << endl;
#define no cout << "No" << endl;
#define umapi unordered_map<ll, ll>
#define umapc unordered_map<char, int>
#define endl "\n"
#define pui pair<int, pair<int,int> >
using namespace std;



/*
            ॐ
    || Jai Shree Ram ||  
 
 */

void solve(){
    
    int x , y;
    cin>>x>>y;

    if(y%2 == 1) {
        no;
        return;
    }

    if(y >= 2*x && y<= 4*x) {
        yes;
        return;
    }

    no;


}

 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout<<fixed<<setprecision(25);
    int t = 1;
    // //cin >> t;
    while (t--)
    {
        solve();
    }
}



Measured memory_bytes: 3568
#include <bits/stdc++.h>
#include <cassert>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using Graph = vector<vector<int>>;

// const long long MOD = 1000000007;
const long long INF = 1LL << 60;
const int INT_INF = 1000000000;

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

// modint
const int MOD = 998244353;

class mint
{
  ll x;

public:
  mint(ll x = 0) : x((x % MOD + MOD) % MOD) {}
  mint operator-() const
  {
    return mint(-x);
  }

  mint &operator+=(const mint &a)
  {
    if ((x += a.x) >= MOD)
      x -= MOD;
    return *this;
  }

  mint &operator-=(const mint &a)
  {
    if ((x += MOD - a.x) >= MOD)
      x -= MOD;
    return *this;
  }

  mint &operator*=(const mint &a)
  {
    (x *= a.x) %= MOD;
    return *this;
  }

  mint operator+(const mint &a)
  {
    mint res(*this);
    return res += a;
  }

  mint operator-(const mint &a)
  {
    mint res(*this);
    return res -= a;
  }

  mint operator*(const mint &a)
  {
    mint res(*this);
    return res *= a;
  }

  mint pow(ll t) const
  {
    if (!t)
      return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1)
      a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const
  {
    return pow(MOD - 2);
  }

  mint &operator/=(const mint &a)
  {
    return (*this) *= a.inv();
  }

  mint operator/(const mint &a)
  {
    mint res(*this);
    return res /= a;
  }

  friend ostream &operator<<(ostream &os, const mint &m)
  {
    os << m.x;
    return os;
  }
};

const int MAX = 510000;
// const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit()
{
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (int i = 2; i < 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;
  }
}

// 二項係数計算
long long COM(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;
}

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

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N, M, K;
  cin >> N >> M >> K;
  COMinit();
  mint ans = 0;
  for (int i = 0; i <= K; i++)
  {
    mint tmp = COM(N - 1, i);
    tmp *= M;
    tmp *= modpow(M - 1, N - i - 1, MOD);
    ans += tmp;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 15568
#include<string>
#include<vector>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<sstream>
#include<functional>
#include<map>
#include<stack>
#include<set>
#include<cmath>

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

#define EPS 1e-6

using namespace std;

int main(){

	int n;
	double x1,y1,x2,y2,x3,y3,x4,y4;

	cin >> n;

	rep(i,n){

	cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;

	double a=y2-y1; double b=x2-x1;
	double d=y4-y3; double e=x4-x3;

	if(a*e-d*b==0) cout << "YES" << endl;
	else cout << "NO" << endl;

	}

	return 0;
}

Measured memory_bytes: 1224
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log2
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
D, G = MAP()
pc = [LIST() for _ in range(D)]

count_min = 1001

for i in range(1<<D):
	count = 0
	sum = 0
	i = list("{:b}".format(i).zfill(D))
	#print(i)
	for j in range(D):
		if i[j] == "1":
			count += pc[j][0]
			sum += pc[j][0]*100*(j+1) + pc[j][1]

	if sum >= G:
		if count < count_min:
			#print("更新", count_min, ">", count)
			count_min = count

	else:
		for j in range(D-1, -1, -1):
			if i[j] == "0":
				remain_count = ceil((G-sum)/(100*(j+1)))
				#print(remain_count)
				if remain_count >= pc[j][0]:
					count = 1001
					break
				else:
					count += remain_count

				if count < count_min:
					#print("更新", count_min, ">", count)
					count_min = count

print(count_min)



Measured memory_bytes: 14244
#include "bits/stdc++.h"
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define BUGAVOID(x) x
#define rep(...) BUGAVOID(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define sz(c) (int)(c.size())
#define all(c) c.begin(),c.end()
#define mp make_pair
#define write(x) cout<<(x)<<"\n"
using namespace std; typedef long long ll;
typedef vector<int> vi; typedef vector<ll> vll; template<class T, class U>using vp = vector<pair<T, U>>;
template<class T>using vv = vector<vector<T>>; template<class T, class U>using vvp = vv<pair<T, U>>;
template<class T>vv<T> vvec(size_t n, size_t m, T v) { return vv<T>(n, vector<T>(m, v)); }
template<class T>bool chmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template<class T>bool chmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
constexpr int INF = 1 << 28, MAX = 1e5 + 5, MOD = 1e9 + 7;
constexpr ll LINF = 1ll << 60; constexpr double EPS = 1e-6;
constexpr int dy[4] = { 0,1,0,-1 }, dx[4] = { 1,0,-1,0 };
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); }; }aaaa;

int N;
vi H;

int main() {
    cin >> N;
    H.resize(N);
    rep(i, N) cin >> H[i];

    int M = H[0];
    int cnt = 1;
    rep(i, 1, N) {
        if (H[i] >= M) cnt++;

        M = max(M, H[i]);
    }

    write(cnt);
}

Measured memory_bytes: 256
n, a, b = map(int, input().split())
if (a - 1) >= (n - b):
    count = (n-b)
    a = a + (n - b)
    b = n
else:
    count = (a - 1)
    b = b - (a - 1)
    a = 1
#print(count)
if ((b - a) % 2 == 0):
    print(min(min(b-1,n-a),(b-a)//2))
elif a == 1 and (b - a) % 2 != 0:
    print(min(min(b - 1, n - a), (b - 1 - a) // 2 + 1) + count)
    #print(count)
elif b == n and (b - a) % 2 != 0:
    print(min(min(b - 1, n - a), (b - 1 - a) // 2 + 1)+count)
else:
    print(min(b-1,n-a)+count)

Measured memory_bytes: 3064
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <bitset>
#include <string>
#include <cmath>
#include <complex>
#include <numeric>
#include <cassert>

#include <vector>
#include <array>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <utility>

#define int64 long long
#define uint64 unsigned long long
using namespace std;

int main()
{
	int64 nn, tmp, ans;
	cin >> nn;
	set<int64> aa;
	for(int64 ii = 0;ii < nn;ii++)
	{
		cin >> tmp;
		aa.insert(tmp);
	}
	ans = aa.size();
	if(ans % 2 == 0)
	{
		ans--;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 8148
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rep(i, l, r) for(int i = (l); i < (r); ++i)
#define dd(x) cout << #x << " = " << x << ", "
#define de(x) cout << #x << " = " << x << endl
//-------
int a, b;
int main() {
	scanf("%d%d", &a, &b);
	if(a > b) swap(a, b);
	if(a >= 2 && b >= 2) {
		printf("%lld\n", 1ll *(a - 2) * (b - 2));
	} else {
		if(a == b && a == 1) printf("1\n");
		else printf("%d\n", max(b - 2, 0));
	}
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int MOD = 1e9 + 7;

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

  ll r8 = 1, r9 = 1, r10 = 1;
  for (int i = 0; i < n; i++) {
    (r8 *= 8) %= MOD;
    (r9 *= 9) %= MOD;
    (r10 *= 10) %= MOD;
  }
  cout << (r10 + 2 * (MOD - r9) + r8) % MOD << endl;
}


Measured memory_bytes: 3632
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>

int main()
{
	int a, b;


	for (a = 1; a < 10; a++) {
		for (b = 1; b < 10; b++) {
			printf("%dx%d=%d\n", a, b, a*b);
		}
	}
	return 0;
}



Measured memory_bytes: 2044
#include <iostream>
using namespace std;
int main(){
        int h,w;
        cin >> h >> w;
        int c[10][10];
        for(int i=0; i<10; i++) {
                for(int j=0; j<10; j++) {
                        cin >> c[i][j];
                }
        }
        for(int k=0; k<10; k++) {
                for(int i=0; i<10; i++) {
                        for(int j=0; j<10; j++) {
                                if(c[i][j]>c[i][k]+c[k][j]) {
                                        c[i][j]=c[i][k]+c[k][j];
                                }
                        }
                }
        }
        int a;
        int res=0;
        for(int i=0; i<h; i++) {
                for(int j=0; j<w; j++) {
                        cin >> a;
                        if(a>=0) {
                                res+=c[a][1];
                        }
                }
        }
        cout << res << endl;
}


Measured memory_bytes: 256
while True:
    n, m = map(int, input().split())  # 品物個数n, 最大の金額m
    if n == 0:
        break

    A = list(map(int, input().split()))
    # print(A)
    ans = 0
    for i in range(len(A)):
        for j in range(i+1, len(A)):
            if A[i] + A[j] > m:
                continue
            else:
                ans = max(ans, A[i]+A[j])

    if ans == 0:
        print('NONE')
    else:
        print(ans)



Measured memory_bytes: 5628
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner scanner = new Scanner(System.in);
		int min = scanner.nextInt();
		boolean notPrime = false;
		int ans = 0;
		for(int i = min; i < 1000000; i++){
			notPrime = false;
			for(int j = 2; j < i; j++){
				if(i % j == 0){
					notPrime = true;
					break;
				}
			}
			if(!notPrime){
				ans = i;
				break;
			}
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 23764
#include <stdio.h>
#include <vector>
#include <limits>
#include <algorithm>

/*
??????
*/


int main() {
	int n;
	std::vector<int> price;

	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		int b;
		scanf("%d", &b);
		price.push_back(b);
	}

	int pmin = std::numeric_limits<int>::max();
	int maxprofit = std::numeric_limits<int>::min();
	for (auto p = price.begin(); p != price.end(); p++) {
		maxprofit = std::max(maxprofit, *p - pmin);
		pmin = std::min(pmin, *p);
	}

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

Measured memory_bytes: 3384
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef int Int;
typedef pair<Int,Int> pii;
typedef pair<Int,double> pid;
typedef pair<double,double> pdd;
typedef pair<Int,pii> pip;
typedef pair<double,Int> pdp;
#define A first
#define B second
#define pb(x) push_back(x)
#define ALL(x) x.begin(),x.end()
#define SZ(x) (x).size()
#define CLR(x) memset(x,0,sizeof x)
#define pdebug() printf("%d\n",__LINE__)
#define Itype(a) typeof(a.begin()) 
#define REP(i,a,b) for(int i = (a);i <= (b);i++)
#define FORO(i,n) REP(i,0,(int)n-1)
#define FORI(i,n) REP(i,1,(int)n)
#define FORIT(i,t) for(Itype(t) i = t.begin();i != t.end();i++)
#define eps 1e-6
#define sqr(x) ((x)*(x))
#define dist(_a,_b) sqrt(sqr(_a.A-_b.A)+sqr(_a.B-_b.B))
#define norm(_a) sqrt(sqr(_a.A)+sqr(_a.B))
template<typename T>void getMin(T &a,T b) { if(a > b) a = b; }
template<typename T>void getMax(T &a,T b) { if(a < b) a = b; }
const int MOD = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int H, W, h, w;
    cin >> H >> W >> h >> w;
    cout << max(0, H * W - h * W - (H - h) * w) << endl; 
    return 0;
}

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

using namespace std;

int mod_pow(int x, int y, int MOD, vector<int> &vc){
    long long ans = 1;
    for(int i=0; i<y; i++){
        ans*=x;
        ans%=MOD;
        vc[i+1]=ans;
    }
    return ans;
}

int main(){
    string s;
    int const MOD=pow(10,9)+7;
    long long A=0;
    long long AB=0;
    long long ABC=0;
    int cnt=0;
    int num=0;
    cin >> s;

    for(int i=0; i<s.size(); i++){
        char x=s[i];
        if (x=='?'){
            num++;
        }
    }

    vector<int> mPow(num+1,1);
    mod_pow(3,num,MOD,mPow);


    for(int i=0; i<s.size(); i++){
        char x = s[i];
        if(x=='A'){
            A+=1*mPow[cnt];
        }else if(x=='B'){
            AB+=A;
        }else if(x=='C'){
            ABC+=AB;
        }else{
            ABC*=3;
            ABC+=AB;
            AB*=3;
            AB+=A;
            A*=3;
            A+=mPow[cnt];
            cnt++;
        }
        A%=MOD;
        AB%=MOD;
        ABC%=MOD;
    }
    cout << ABC << '\n';
}

Measured memory_bytes: 896
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}

func main() {
	fp := os.Stdin
	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(os.Stdout)

	n := getNextInt(scanner)
	z := getNextInt(scanner)
	w := getNextInt(scanner)

	aa := make([]int, n+1)

	aa[0] = w
	for i := 0; i < n; i++ {
		aa[i+1] = getNextInt(scanner)
	}

	ans := solve(n, z, w, aa)
	fmt.Fprintln(writer, ans)

	writer.Flush()
}

func solve(n, z, w int, aa []int) int {
	dpx := make([]int, n+1)
	dpy := make([]int, n+1)
	for i := 1; i < n; i++ {
		dpx[i] = -1
		dpy[i] = -1
	}
	return playx(1, n, aa, dpx, dpy)
}

func playx(i, n int, aa, dpx, dpy []int) int {
	if i == n {
		return absint(aa[i] - aa[i-1])
	}
	if dpx[i] >= 0 {
		return dpx[i]
	}
	ans := -1
	for ii := i + 1; ii <= n; ii++ {
		ans = maxint(ans, playy(ii, n, aa, dpx, dpy))
	}

	ans = maxint(ans, absint(aa[n]-aa[i-1]))
	dpx[i] = ans

	return ans
}

func playy(i, n int, aa, dpx, dpy []int) int {
	if i == n {
		return absint(aa[i] - aa[i-1])
	}
	if dpy[i] >= 0 {
		return dpy[i]
	}

	ans := int(1e9 + 1)
	for ii := i + 1; ii <= n; ii++ {
		ans = minint(ans, playx(ii, n, aa, dpx, dpy))
	}

	ans = minint(ans, absint(aa[n]-aa[i-1]))
	dpy[i] = ans
	return ans
}

func absint(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func maxint(a int, b int) int {
	if a > b {
		return a
	}
	return b
}
func minint(a int, b int) int {
	if a < b {
		return a
	}
	return b
}


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

a,b,c,x,y = map(int, input().split())

cost = float('inf')
mz = max(x,y)*2
for z in range(1,mz+1):
    #print(z, (a*x + b*y), a*(x-0.5*z) + b*(y-0.5*z) + c*z)
    if z > 0:
        cost = min(cost, a*max((x-0.5*z),0) + b*max((y-0.5*z),0) + c*z)
cost = int(min(cost, a*x + b*y))
print(cost)

Measured memory_bytes: 3064
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

count = 0

for i in range(n):

    if i == 0:
        count += b[a[i]-1]

    else:
        count += b[a[i]-1]

        if a[i] - a[i-1] == 1:
            count += c[a[i-1]-1]

print(count)

Measured memory_bytes: 3064
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
char s[1100];
int main()
{
	scanf("%s", s);
	string t = "";
	if(strlen(s) < 4) printf("No\n");
	else {
		for (int i = 0; i < 4; i++) {
			t += s[i];
		}
		if(t == "YAKI") printf("Yes\n");
		else printf("No\n");
	}
}

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

int main() {
  
  int N;
  cin >> N;
  
  vector<int> a(N);
  int sum = 0;
  
  for (int i = 0; i < N; ++i){
    cin >> a.at(i);
    sum += a.at(i);
  }
  
  int mini = sum;
  int prefix_sum = 0;
  
  for ( int i = 0; i < N; ++i){
    prefix_sum += a.at(i);
    mini = min(mini, abs(prefix_sum - (sum - prefix_sum)));
  }
  
  cout << mini << endl;
  return 0;
 
}

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

int n, m;
int c[1010], d[1010];

int dp[1010][1010];

int dfs(int i=0, int j=0)
{
  if (i == n) return 0;
  if (j == m) return 1e9;

  int &ret = dp[i][j];
  if (dp[i][j] != -1) return ret;
  
  ret = min(dfs(i + 1, j + 1) + d[i] * c[j], dfs(i, j + 1));

  return ret;
}

int main()
{
  memset(dp, -1, sizeof(dp));

  cin >> n >> m;
  for (int i = 0; i < n; i++){
    cin >> d[i];
  }
  for (int i = 0; i < m; i++){
    cin >> c[i];
  }

  cout << dfs() << endl;
}

Measured memory_bytes: 7088
<?php
list($N,$L) = explode(" ",trim(fgets(STDIN)));
$a = explode(" ",trim(fgets(STDIN)));

$sum = array_sum($a);

if($sum < $L){
    echo "Impossible";
}elseif($sum == $L){
    if($N == 2){
        echo "Possible\n";
        echo 1;
    }else{
        echo "Impossible";
    }
}else{
    for($i = 0;$i < $N - 1;$i++){
        $sum2[] = $a[$i] + $a[$i + 1];
    }
    if(max($sum2) >= $L){
        echo "Possible\n";
        $num = array_search(max($sum2),$sum2);
        if($num == 0){
            for($i = $N - 1;$i > 0;$i--){
                echo $i ."\n";
            }
        }elseif($num == $N - 1){
            for($i = 1;$i < $N;$i++){
                echo $i ."\n";
            }
        }else{
            for($i = 1;$i < $num + 1;$i++){
                echo $i ."\n";
            }
            for($i = $N - 1;$i > $num;$i--){
                echo $i ."\n";
            }
        }
    }else{
        echo "Impossible";
    }
}

Measured memory_bytes: 35912
uses math;
var
  i,j,k,n,m,a,b,c,x,y:longint;
begin
     read(a,b);
if (a<=0) and (b>=0) then writeln('Zero')
  else if (a>=0)and(b>=0) then writeln('Positive')
   else if (a<0)and((b-a+1) mod 2=0) then writeln('Positive')
     else writeln('Negative');
  end.

Measured memory_bytes: 128
N, M = map(int, input().split())
arr = [0 for _ in range(M)]
for i in range(M):
    p, y = map(int, input().split())
    arr[i] = [p, y, i]

arr.sort(key=lambda x: x[1])

arr[0][1] = 1
P_cnt = [1 for _ in range(10 ** 6)]
ans_list = [0] * M
for p, y, i in arr:
    ans_list[i] = [str(p).zfill(6) + str(P_cnt[p]).zfill(6), i]
    P_cnt[p] += 1

ans_list.sort(key=lambda x: x[1])
for i in range(M):
    print(ans_list[i][0])

Measured memory_bytes: 49252
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <string>
#pragma warning(disable : 4996)



int left(int i) {
	return i * 2;
}
int right(int i) {
	return i * 2 + 1;
}

void maxHeapify(std::vector<int> &A, int i) {
	int l = left(i);
	int r = right(i);
	int largest = i;
	if ((A.size() > l) && (A[l] > A[i])) {
		largest = l;
	}
	if ((A.size() > r) && (A[r] > A[largest])) {
		largest = r;
	}
	if (largest != i) {
		int tmp = A[largest];
		A[largest] = A[i];
		A[i] = tmp;
		maxHeapify(A, largest);
	}
}
void buildMaxHeap(std::vector<int> &A) {
	for(int i = A.size()/2; i >= 1; --i) {
		maxHeapify(A, i);
	}
}
void insertMaxHeap(std::vector<int> &A, int v) {
	A.push_back(v);
	int i = A.size() - 1;
	while (i > 1) {
		int parent = i / 2;
		if (A[i] > A[parent]) {
			int tmp = A[parent];
			A[parent] = A[i];
			A[i] = tmp;
			i = parent;
		}
		else {
			break;
		}
	}
}
int extract(std::vector<int> &A) {
	if (A.size() < 2) return -1;
	int max = A[1];
	A[1] = A[A.size()-1];
	A.pop_back();
	maxHeapify(A, 1);
	return max;
}
int main(void) {
	std::vector<int> A;
	A.push_back(-1); // dummy
	while (1) {
		char line[1024];
		scanf("%s", &line[0]);
		if (strcmp(line, "end") == 0) break;
		if (strcmp(line, "insert") == 0) {
			int v;
			scanf("%d", &v);
			insertMaxHeap(A, v);
		}
		if (strcmp(line, "extract") == 0) {
			int max = extract(A);
			printf("%d\n", max);
		}
	}
	return 0;
}



Measured memory_bytes: 6500
N = int(input())
A = []
for i in range(N):
    A.append(int(input()))
sorted_A = list(set(A))
max_A = sorted_A[-1]
max_nums = set(i for i, v in enumerate(A) if v == max_A)
if len(max_nums) > 1:
    for i in range(N):
        print(max_A)
else:
    max2_A = sorted_A[-2]
    for i in range(N):
        if i in max_nums:
            print(max2_A)
        else:
            print(max_A)


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

int main()
{
    int n;
    cin >> n;
    vector<int> ds(n);
    for(int i=0; i<n; i++)
    {
        cin >> ds.at(i);
    }

    ll sum = 0;
    for(int i=0; i<n; i++)
    {
        for(int j=i+1; j<n; j++)
        {
            sum += ds.at(i) * ds.at(j);
        }
    }

    cout << sum << endl;

    return 0;
}


Measured memory_bytes: 256
import java.io.File;
import java.io.IOException;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Deque;
import java.util.List;
import java.util.Scanner;

public class Main {
 
	public static void main(String[] args) throws IOException {
		//File file = new File("input.txt");
		//Scanner in = new Scanner(file);
		
		Scanner in = new Scanner(System.in);
		
		int A = in.nextInt();
		int B = in.nextInt();
		int C = in.nextInt();
		System.out.println((C >= A && C <= B) ? "Yes" : "No");
	}
}


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

const char NL = '\n';
const char SP = ' ';
#define loop(i, a, b) for (int i = a; i < b; i++)

int main () {
  ios_base::sync_with_stdio(false);
  string s;
  int sum;
  cin >> s;
  loop (i, 0, s.size()) {
    sum += int (s[i]) - 48;
    sum %= 9;
  }
  if (sum % 9 == 0) {
    cout << "Yes\n";
  }
  else {
    cout << "No\n";
  }
  return 0;
}

Measured memory_bytes: 3708
// This file is a "Hello, world!" in C++ language by GCC for wandbox.
#include <iostream>
#include <cstdlib>

using namespace std;

int main()
{
    //int 1, 3, 50
    //double 2.9, 4.8, 1.0
    //char 'a', 'x' 
    //string "ax", "kurisu"
    
    int n; 
    cin >> n;
    
    int answer = 0;
    for (int i = 1; i <= n; i++) {
        answer += i;
    }
    
    cout << answer << endl;
}

// GCC reference:
//   https://gcc.gnu.org/

// C++ language references:
//   https://cppreference.com/
//   https://isocpp.org/
//   http://www.open-std.org/jtc1/sc22/wg21/

// Boost libraries references:
//   https://www.boost.org/doc/


Measured memory_bytes: 3544
{-# LANGUAGE BangPatterns #-}
import Control.Arrow
import Control.Monad.Fix
import Data.Char (ord, isDigit)
import Data.Bits
import Data.Int
import Data.List
import qualified Data.Vector.Unboxed as VU
import qualified Data.ByteString.Char8 as B
import System.IO (stdin)

readIONat :: (Bits a, Integral a) => IO a
readIONat = do
  let reader ch = fromIntegral $ ord ch - ord '0'

  digit0 <- fix
    (\(!f) (!_) -> do
      ch <- fmap B.head $ B.hGetSome stdin 1
      if isDigit ch then return (reader ch) else f ch
    )
    ' '
  flip fix (return digit0) $ \(!f) (!acc) -> do
    s <- B.hGetSome stdin 1
    if B.null s || not (isDigit (B.head s))
      then acc
      else do
        a <- acc
        f (return $ shiftL a 1 + shiftL a 3 + reader (B.head s))

solve :: Int -> VU.Vector Int16 -> Int32
solve n hs = fst dp
 where
  -- dp[i]: minimal cost of moving from 1st to i-th place
  dp :: (Int32, Int32)
  dp = VU.foldl'
    (\(!dp1, !dp2) (!i, !v) -> if i == 0
      then (0, dp1)
      else if i == 1
        then (dp1 + abs (fromIntegral $ v - hs VU.! 0), dp1)
        else
          ( min (dp1 + abs (fromIntegral $ v - hs VU.! (i - 1)))
                (dp2 + abs (fromIntegral $ v - hs VU.! (i - 2)))
          , dp1
          )
    )
    (-1, -1)
    (VU.indexed hs)

main = do
  n  <- readIONat
  hs <- VU.replicateM n readIONat
  print $ solve n hs


Measured memory_bytes: 1404
import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		
		String S=sc.next();
		String ans="";
		
		for(int i=0;i<S.length();i++) {
			
			if(S.charAt(i)=='0')
				ans+="0";
			if(S.charAt(i)=='1')
				ans+="1";
			if(S.charAt(i)=='B') {
				if(ans.length()>0)
					ans=ans.substring(0,ans.length()-1);
			}
		}
		
		System.out.println(ans);
		
		sc.close();
	}
}

Measured memory_bytes: 21588
/* HARDWORK IS THE KEY TO SUCCESS.
       RATING IS TEMPORARY , KNOWLEDGE IS PERMANENT.!!!*/
    #include <bits/stdc++.h>
    #define pragma
    using namespace std;
    #define ll long long
    #define ld long double
    #define T ll t = 1; cin>>t; while(t--)
    #define vin ll n; cin>>n; vector<ll>x(n); for(ll i=0; i<n; i++) cin>>x[i]
    #define vout for(ll i=0; i<n; i++) cout<<x[i]<<" "
    #define ain ll n,k,i; cin>>n>>k; ll a[k]; for( i=0; i<k; i++) cin>>a[i]
    #define aout for(ll i=0; i<n; i++) cout<<a[i]<<" "
    #define matin ll m,n; cin >> n >> m; ll a[n + 1][m + 1] ; for(ll i=1;i<=n;i++) for(ll j=1;j<=m;j++) cin>>a[i][j];
    #define matout for(ll i=0;i<m;i++){for(ll j=0;j<n;j++) cout<<a[i][j]<<" "; cout<<"\n";}
    #define sin set<ll>s; ll n; cin>>n; ll tmp; for(ll i=0;i<n;i++){cin>>tmp; s.I(tmp);}
    #define sout for(auto it=s.begin();it!=s.end();++it) cout<<*it<<" "
    #define F first
    #define S second
    #define I insert
    #define pb push_back
    #define ppb pop_back
    #define AISORT sort(a,a+n)
    #define ADSORT sort(a,a+n,greater<ll>())
    #define VISORT sort(x.begin(),x.end())
    #define VDSORT sort(x.begin(),x.end(),greater<ll>())

    const ll maxs = 1e5+3;
    const ll maxs1 = 1e3+4;
    const ll mod = 1e9 + 7;

    //MODULO OPEARTIONS
    inline ll add(ll a, ll b) { return (mod + a + b) % mod; }
    inline ll sub(ll a, ll b) { return (a - b + mod) % mod; }
    inline ll mul(ll a, ll b) { return (1ll * a * b) % mod; }

    //POWER
    ll fastpow(ll x,ll y)
    {ll res = 1;x = x % mod;while (y > 0){ if (y & 1)res = (res * x) % mod; y = y >> 1 ; x = (x * x) % mod; } return res;}

    //MODULAR INVERSE
    ll inv(ll x){ return fastpow(x , mod - 2);}

//     ll n;
//     ll a[maxs];
//     ll tree[maxs];
    bool vis[maxs];
    vector<ll>graph[maxs];
    //ALWAYS CLEAR THEM WHEN TESTCASES ARE GIVEN
    //ALWAYS RETURN WHEN ST == ED CONDITION IN SEGMENT TREES


    int main()
    {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        ain;
        ll sum = 0;
        for(i = 0;i < k;++i)
            sum += a[i];
        if(sum > n)
        {
            cout << -1;
        }
        else
            cout << n - sum;
    }

Measured memory_bytes: 6004
import java.util.*;
import java.text.*;

public class Main {

    Scanner sc = new Scanner(System.in);
    int d = sc.nextInt();
    int g = sc.nextInt();
    int[][] arr = new int[d][2];
    int res = (int)1e5;

    public static void main(String[] args) {
        new Main().run();
    }

    void run() {

        for (int i=0; i<d; i++) {
            arr[i][0] = sc.nextInt();
            arr[i][1] = sc.nextInt();
        }

        dfs("");

        System.out.println(res);

    }

    void dfs(String s) {
        if (s.length()==d) {
//            System.out.println(s);
            int sum = 0;
            int cnt = 0;
            for (int i=0; i<d; i++) {
                if (s.charAt(i)=='1') {
                    sum += arr[i][0] * 100 * (i+1) + arr[i][1];
                    cnt += arr[i][0];
                }
            }
            sum = g - sum;
//            System.out.println(sum);
            if (sum<=0) {
//                System.out.println(cnt);
                res = Math.min(res, cnt);
            } else {
                for (int i=d; 1<=i; i--) {
                    if (s.charAt(i-1)=='0') {
                        int max = arr[i-1][0]-1;
                        int need = sum%(100*i)==0 ? sum/(100*i) : (sum/(100*i))+1;
                        if (need<=max) {
                            cnt += need;
                            sum -= (100*i)*need;
                            if (sum<=0) break;
                        } else {
                            sum -= (100*i)*max;
                            cnt += max;
                            if (sum<=0) break;
                        }
                    }
                }
//                System.out.println(cnt);
                if (sum<=0) res = Math.min(res, cnt);
            }

        } else {
            for (int i=0; i<2; i++) {
                dfs(s + i);
            }
        }
    }

//    void dfs(String s) {
//        if (split(s, 'T')==d-1) {
//            System.out.println(s);
//            String[] ts = s.split("T", 0);
//            int[] a = new int[d];
//            int cnt = 0;
//            for (int i=0; i<d; i++) a[i] = Integer.parseInt(ts[i]);
//            int sum = 0;
//            for (int i=0; i<d; i++) {
//                cnt += a[i];
//                sum += a[i] * 100 * (i+1);
//                if (a[i]==arr[i][0]) sum += arr[i][1];
//            }
//            if (g<=sum) res = Math.min(res, cnt);
//        }
//        else {
//            for (int i=0; i<d; i++) {
//                for (int j=0; j<=arr[i][0]; j++) {
//                    dfs(s + j + "T");
//                }
//            }
//        }
//    }
//
//    int split(String s, char c) {
//        return s.split(c + "").length - 1;
//    }


}


Measured memory_bytes: 21844
from collections import deque
import copy

def BFS(sy,sx,xy_list):
 dist=[[-1]*w for i in range(h)]
 dist[sy][sx]=0
 xy_list[sy][sx]='#'

 dq=deque()
 dq.append((sy,sx))

 while dq:
  y,x=dq.popleft()
  for dy,dx in [[1,0],[-1,0],[0,1],[0,-1]]:
   ny=y+dy
   nx=x+dx
   if 0<=ny<h and 0<=nx<w and xy_list[ny][nx]!='#':
    dq.append((ny,nx))
    xy_list[ny][nx]='#'
    dist[ny][nx]=dist[y][x]+1

 return dist

h,w=map(int,input().split())
s=[list(input()) for i in range(h)]

ans=0
for hh in range(h):
 for ww in range(w):
  if s[hh][ww]=='#':
   continue
  xy_list=copy.deepcopy(s)
  dist=BFS(hh,ww,xy_list)
  for d in dist:
   ans=max(ans,max(d))

print(ans)

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

#define ff first
#define ss second
#define mp make_pair

using namespace std;

typedef long long ll;

vector<int> l[200005];
vector<pair<int,int>> r[200005];
ll dp[200005], st[800005], lp[800005];

void prop(int p, bool leaf) {
	if(lp[p]) {
		st[p] += lp[p];
		if(!leaf) {
			lp[2*p] += lp[p];
			lp[2*p+1] += lp[p];
		}
		lp[p] = 0;
	}
}

void add(int L, int R, int i, int j, ll num, int p) {
	if(R < i or L > j) return;
	if(L >= i and R <= j) {
		lp[p] += num;
		prop(p, L == R);
		return ;
	}

	int M = (L+R)/2;
	prop(2*p, L == M);
	prop(2*p+1, M+1 == R);

	add(L, M, i, j, num, 2*p);
	add(M+1, R, i, j, num, 2*p+1);

	st[p] = max(st[2*p], st[2*p+1]);
}

ll query(int L, int R, int i, int j, int p) {
	if(R < i or L > j) return -1e18;
	if(L >= i and R <= j) return st[p];

	int M = (L+R)/2;

	prop(2*p, L == M);
	prop(2*p+1, M+1 == R);

	return max(query(L, M, i, j, 2*p), query(M+1, R, i, j, 2*p+1));
}

int main() {
	int n,a,b,c,m;
	scanf("%d %d", &n, &m);

	for(int i = 0; i < m; i++) {
		scanf("%d%d%d", &a, &b, &c);
		l[a].push_back(c);
		r[b+1].push_back(mp(a,c));
	}

	ll ans = 0;
	for(int i = 1; i <= n; i++) {
		for(int x : l[i])
			add(0, n, 0, i-1, x, 1);
		for(auto& x : r[i])
			add(0, n, 0, x.ff-1, -x.ss, 1);


		dp[i] = query(0, n, 0, i-1, 1);
		add(0, n, i, i, dp[i], 1);

		ans = max(ans, dp[i]);
	}

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

    return 0;
}


Measured memory_bytes: 36224
def rate(n:int) ->str:
    if 1 <= n <= 399:
        return 'hai'
    elif n <= 799:
        return 'cha'
    elif n <= 1199:
        return 'mido'
    elif n <= 1599:
        return 'mizu'
    elif n <= 1999:
        return 'ao'
    elif n <= 2399:
        return 'ki'
    elif n <= 2799:
        return 'dai'
    elif n <= 3199:
        return 'aka'
    else:
        return 'neutral'

def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    d = {}
    n_count = 0
    for aa in a:
        buf = rate(aa)
        if buf == 'neutral':
            n_count += 1
            continue
        if buf not in d:
            d[buf] = 0
        d[buf] += 1
    if n_count >= 1:
        if d:
            print(len(d.values()),len(d.values()) + n_count)
        else:
            print('1',n_count)
    else:
        print(len(d.values()),len(d.values()))

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
/*
      HET PAGHADAR
      DA-IICT
      @HET262
*/
 
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#define oos tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
using namespace __gnu_pbds; 
typedef long double ld;
typedef long long ll;
typedef vector<ll> vec; 
#define inf LLONG_MAX
#define bp __builtin_popcountll
#define pb push_back
#define ff first
#define ss second
#define P pair<ll,ll>
#define N 1000005
#define mod 1000000007
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int32_t main()
{
      
      FAST;
      
      ll n,ans=0;
      cin>>n;
      
      ll tt=inf;
      for(int i=1;i<=n;i++)
      {
            ll x;
            cin>>x;
            tt=min(tt,x);
            
            if(tt>=x)
                  ans++;
      }
      
      cout<<ans;
      
}


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

struct treetype {
	int parent;
	int sibling;
	int degree;
	int depth;
	int height;
	char type[20];
	int left;
	int right;
};

int main(void) {
	int n;
	struct treetype tree[26];
	int i, j, k;
	int depthmax = 0;
	int number = 0;
	int roottr = 0;

	scanf("%d", &n);

	for (i = 0; i < n; i++) {
		tree[i].parent = -2;
	}

	for (i = 0; i < n; i++) {
		scanf("%d", &number);
		scanf("%d %d", &tree[number].left, &tree[number].right);

		tree[tree[number].left].parent = number; //親決定
		tree[tree[number].left].sibling = tree[number].right;
		tree[tree[number].right].parent = number;
		tree[tree[number].right].sibling = tree[number].left;
		tree[number].degree = 0;
		tree[number].height = 0;
		if (tree[number].left >= 0) {
			tree[number].degree += 1;
		}
		if (tree[number].right >= 0) {
			tree[number].degree += 1;
		}
	}

	for (i = 0; i < n; i++) {
		if (tree[i].parent == -2 && roottr == 0) {
			strcpy(tree[i].type, "root");
			tree[i].sibling = -1;
			tree[i].parent = -1;
			roottr = 1;
		}
		else if (tree[i].left >= 0 || tree[i].right >= 0) {
			strcpy(tree[i].type, "internal node");
		}
		else {
			strcpy(tree[i].type, "leaf");
		}
	}

	for (i = 0; i < n; i++) {
		k = i;
		for (j = 0; 1; j++) {
			if (tree[k].parent < 0) {
				tree[i].depth = j;
				if (depthmax < tree[i].depth) {
					depthmax = tree[i].depth;
				}
				break;
			}
			k = tree[k].parent;
		}
	}

	for (i = 0; i < n; i++) {
		if (strcmp(tree[i].type, "leaf") == 0) {
			k = i;
			for (j = 1; 1; j++) {
				if (tree[k].parent < 0) {
					break;
				}
				else {
					k = tree[k].parent;
				}
				if (j > tree[k].height) {
					tree[k].height = j;
				}
			}
		}
	}

	for (number = 0; number < n; number++) {
		printf("node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, %s\n", number, tree[number].parent, tree[number].sibling, tree[number].degree, tree[number].depth, tree[number].height, tree[number].type);
	}

	return 0;
}


Measured memory_bytes: 2104
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys

input = sys.stdin.readline

cnt = 0

def main():
    N, X = map(int, input().split())
    L = [int(e) for e in input().split()]

    def rec(i, d):
        global cnt
        if d > X:
            return
        cnt += 1
        if i >= N:
            return
        return rec(i+1, d + L[i])

    rec(0, 0)
    print(cnt)


main()


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

int main() {
    ll n;
    std::cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    ll ans = 0;
    
    while(true){
        ll sum = 0;
        vector<ll> tmp(n);
        for (int i = 0; i < n; i++) {
            sum += a[i]/n;
            tmp[i]=a[i]/n;
            a[i]%=n;
        }
        ans += sum;
        if(sum==0){
            std::cout << ans << std::endl;
            return 0;
        }else{
            for (int i = 0; i < n; i++) {
                a[i] += sum-tmp[i];       
            }
        }
    }
}



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

#define REP(i, x, n) for (int i = x; i < (int)(n); i++)
#define rep(i, n) REP (i, 0, n)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x.size())
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define uniq(x) x.erase(unique(x.begin(), x.end()), x.end())
#define F first
#define S second
#define mp make_pair
#define eb emplace_back

using namespace std;

typedef long long ll;

const int INF = 1 << 29;

int main() {
    string ans[] = {"Positive", "Negative"};
    int a, b;
    cin >> a >> b;
    if (a <= 0 && 0 <= b) cout << "Zero" << endl;
    else if (b < 0 && (abs(a) - abs(b)) % 2 == 0) cout << ans[1] << endl;
    else cout << ans[0] << endl;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Contest
{
    class ABC
    {
        static void Main()
        {
            Solve();
        }
        private static void Solve()
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int a = 1;
            int b = input[1];
            int tap = 0;
            while(a < b)
            {
                a += input[0] - 1;
                tap++;
            }
            Console.WriteLine(tap);
        }
        
    }
}


Measured memory_bytes: 13396
#include <cstdio>
#include <algorithm>

long long dp[3000][3000];
long long a[3000];

long long solve(int l, int r)
{
  if (dp[l][r] != 1e18) return dp[l][r];
  if (l == r)
  {
    dp[l][r] = a[l];
  }
  else
  {
    dp[l][r] = std::max(a[l] - solve(l + 1, r), a[r] - solve(l, r - 1));
  }  
  return dp[l][r];
}

int main()
{
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i)
  {
    scanf("%lld", a + i);
  }
  std::fill((long long*)dp, (long long*)dp + 3000 * 3000, 1e18);
  printf("%lld\n", solve(0, n - 1));
  return 0;
}


Measured memory_bytes: 70656
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <cmath>
# include <functional>
# include <utility>
#include <iomanip>

# define MOD 1000000000+7
# define INF 1000000000
#define rep(i,rept)	for(ll i = 0; i<rept;i++)
typedef long long ll;
using namespace std;
int main() {
	double a, b, c, x;
	cin >> a >> b >> x;
	if (x / a > a* b / 2) {
		//台形
		c = (x * 2 / a / a) - b;
		cout << setprecision(10) << atan((b - c) / a)*180/3.141592653589793238462643383279  << endl;
	}
	else {
		//三角形
		c = x * 2 / a / b;
		cout<< setprecision(10)<< atan(b / c)*180/3.141592653589793238462643383279 << endl;
	}
	
}


Measured memory_bytes: 512