akhauriyash/Code-Regression huggingface dataset:
d,g=map(int,input().split())
a=[]
for i in range(d):a.append(list(map(int,input().split())))
ans=float("inf")
for i in range(2**d):
    i=list(map(int,list(bin(i)[2:].zfill(d))))
    x,y,z=0,0,0
    for j in range(d):
        if i[j]==1:
            x+=a[j][0]
            y+=(j+1)*100*a[j][0]+a[j][1]
        else:z=j
    if g-y>0:
        b=(g-y+z*100)//((z+1)*100)
        if b<a[z][0]:ans=min(ans,x+b)
    else:ans=min(ans,x)
print(ans)

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

#define int long long

using namespace std;


const int MAXN = 200 * 1000 + 23;









int n, a[MAXN], ans;


int32_t main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    if (a[0] != 0) return cout << -1, 0;
    for (int i = 1; i < n; i++)
        if (a[i] - a[i - 1] > 1)
            return cout << -1, 0;
        else
            ans += (a[i] != a[i - 1] + 1? a[i]: 1);
    cout << ans;
    return 0;
}

Measured memory_bytes: 1792
n,m,X,Y= map(int, input().split())
x=[int(_) for _ in input().split()]
y=[int(_) for _ in input().split()]
x.append(X)
y.append(Y)
x.sort(reverse=True)
y.sort()
print('No War' if x[0]<y[0] else 'War')

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

int main(){
  int n,m,now,cou,sin_cou;
  int root[1111],sin[1111];
  while(1){
    cin >> n >> m;
    if(n == 0 && m == 0) break;
    for(int i=0;i<n;i++){
      cin >> root[i];
    }
    for(int i=0;i<m;i++){
      cin >> sin[i];
    }
    cou=0,sin_cou=0,now=1;
    while(now < n){
      now += sin[sin_cou];
      now += root[now-1];
      sin_cou++;
      cou++;
    }
    cout << cou << endl;
  }
}

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

int op(int x, int y) { return max(x, y); }

int e() { return -1; }

int target;

bool f(int v) { return v < target; }

int main()
{
	int n, q, t, x, y;
	scanf("%d%d", &n, &q);
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		scanf("%d", &a[i]);
	}
	segtree<int, op, e> st(a);
	while (q--) {
		scanf("%d", &t);
		if (t == 1) {
			scanf("%d%d", &x, &y);
			st.set(x-1, y);
		}
		else if (t == 2) {
			scanf("%d%d", &x, &y);
			printf("%d\n", st.prod(x-1, y));
		}
		else {
			scanf("%d%d", &x, &target);
			--x;
			printf("%d\n", st.max_right<f>(x)+1);
		}
	}
}

Measured memory_bytes: 6092
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using pint = pair<int,int>;
ll mod = 1000000007,mod2 = 998244353;

void chmin(long long &a, long long b) { if (a > b) a = b; }
void chmax(long long &a, long long b) { if (a < b) a = b; }
const long long INF = 1LL<<60;
ll gcd(ll a,ll b){
    if(b == 0) return a;
    else return gcd(b,a%b);
}

//重みある時
using Edge = pair<int,int>;
using Graph = vector<vector<Edge> >;

ll fac(ll n){
    if(n == 0) return 1;
    ll tmp = 1;
    for (int i = 1; i <= n; ++i) {
        tmp *= i;
    }
    return tmp;
}

int main() {
    int n;
    cin >> n;
    vector<int> p(n),q(n),a(n);
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> q[i];
    }
    ll ans1 = 0,ans2 = 0;

    for (int i = 0; i < n; ++i) {
        a[i] = i+1;
    }
    int it = 0;
    do{
        it++;
        if(a == p) ans1 = it;
        if(a == q) ans2 = it;
    }while(next_permutation(a.begin(),a.end()));
    
    cout << abs(ans1-ans2) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using VI = vector<int>;
using VL = vector<ll>;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);++(i))
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);++(i))
#define rFOR(i,a,n) for(int (i)=(n)-1;(i)>=(a);--(i))
#define erFOR(i,a,n) for(int (i)=(n);(i)>=(a);--(i))
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
#define out(y,x,h,w) (y) < 0 || (h) <= (y) || (x) < 0 || (w) <= (x)
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
const long double pi = acos(-1);
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; }return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; }return 0; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& input, vector<T>& v) { for (auto& elemnt : v)input >> elemnt; return input; }

int n; ll a, b;
VL h;

bool check(ll x) {
    ll cnt = 0;
    ll dam = b * x;
    FOR(i, 0, n) {
        if (h[i] <= dam)continue;
        cnt += (h[i] - dam) / (a - b) + bool((h[i] - dam) % (a - b));
    }
    return cnt <= x;
}

int main() {
    init();

    cin >> n >> a >> b;
    h.resize(n); cin >> h;
    ll ng = 0, ok = INF;
    while (ok - ng > 1) {
        ll mid = (ng + ok) / 2;
        if (check(mid))ok = mid;
        else ng = mid;
    }
    cout << ok << "\n";
}


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

using i64=int64_t;

#define rep(i,x,y) for(i64 i=i64(x),i##_max_for_repmacro=i64(y); i<i##_max_for_repmacro; ++i)
#define debug(x) #x << "=" << (x)
 
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif
 
const int inf=1.01e9;
const i64 inf64=4.01e18;
const double eps=1e-9;
 
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
        os << v << ",";
    }
    os << "]";
    return os;
}

void solve(){
    char X,Y;
    cin >> X >> Y;

    if(X<Y) cout << "<" << endl;
    else if(X>Y) cout << ">" << endl;
    else cout << "=" << endl;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    solve();
    return 0;
}


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

#define ll long long
#define ull unsigned long long
#define mod 1000000007

using namespace std;

struct node {
	ll count;
	vector<int> cNodes;
};

node nodes[200000];

void countIncrease(int t, ll x, int y) {
	nodes[t].count += x;
	for (int i = 0; i < nodes[t].cNodes.size(); i++) {
		if(nodes[t].cNodes[i]-1 != y) countIncrease(nodes[t].cNodes[i] - 1, nodes[t].count, t);
	}
}

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

	unsigned int n, q;
	cin >> n >> q;
	for (int i = 0; i < n - 1; i++) {
		nodes[i].count = 0;
		int a, b;
		cin >> a >> b;
		nodes[a - 1].cNodes.push_back(b);
		nodes[b - 1].cNodes.push_back(a);
	}

	for (int i = 0; i < q; i++) {
		int p;
		ll x;
		cin >> p >> x;

		nodes[p - 1].count += x;
	}

	countIncrease(0, 0, 0);

	cout << nodes[0].count;
	for (int i = 1; i < n; i++) {
		cout << " " << nodes[i].count;
	}

	cout << endl;
}


Measured memory_bytes: 24320
#include<iostream>
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  int arr[n];
  int arr1[n];
  for(int i=0;i<n;i++)
  {
    cin>>arr[i];
    arr1[i]=arr[i];  
  }
  int c=0;
  sort(arr1,arr1+n,greater<>());
  for(int i=0;i<n;i++)
  {
    if(arr[i]==arr1[0])
      cout<<arr1[1]<<endl;
    else
      cout<<arr1[0]<<endl;
  }
}


Measured memory_bytes: 3200
#include<bits/stdc++.h>
#define rep(i,n) for(int i = 0;i<n;i++)
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0;}

int main() {
    string s;
    ll k;
    cin >> s >> k;
    string ans = "1";
    for(int i = 0;i<k;i++) {
        if(s[i] != '1') {
            ans = s[i];
            break;
        }    
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i=0; i<(n); i++)
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
int main(){
    ll n; cin>>n;
    vector<ll> p(n);
    rep(i,n) cin>>p[i];
    ll nin=p[0];
    ll res=0;
    rep(i,n){
        if(p[i]<=nin) res++;
        chmin(nin, p[i]);
    }
    cout<<res<<endl;
    return 0;
}

Measured memory_bytes: 1792
#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;

int main(){

	int n; cin >> n;
	int x[n]={0}, y[n]={0};
	for(int i=0; i<n; ++i){cin>>x[i];}
	for(int i=0; i<n; ++i){cin>>y[i];}
	
	double norm_1=0., norm_2=0., norm_3=0., norm_inf=0.;
	double dif=0.;
	for(int i=0; i<n; ++i){
		dif = abs( (double)x[i] - (double)y[i] );
		norm_1 += dif;
		norm_2 += pow(dif,2);
		norm_3 += pow(dif,3);
		if (norm_inf < dif){norm_inf = dif;}
	}

	cout << fixed << setprecision(7);
	cout << norm_1 << endl;
	cout << pow(norm_2,1/2.) << endl;
	cout << pow(norm_3,1/3.) << endl;
	cout << norm_inf << endl;

	return 0;
}



Measured memory_bytes: 3456
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <vector>

using namespace std;

int main() {
  int n;
  scanf("%d", &n);
  vector<int> d(n);

  for (int i = 0; i < n; i++) {
    int x;
    scanf("%d", &x);
    d[i] = x;
  }

  int sum = 0;
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      sum += d[i] * d[j];
    }
  }

  cout << sum << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <numeric>
#include <functional>
#include <array>
#include <map>
#include <set>

using namespace std;
using P = pair<int, int>;
using T = tuple<int, int, int>;

long long MOD = 1000000007;
long long dp[100005][4];

bool compare_by_second(pair<int, int> a, pair<int, int> b) {
	if (a.second != b.second) {
		return a.second < b.second;
	}
	else {
		return a.first < b.first;
	}
}

int main() {

	string S,T;
	cin >> S >> T;

	int ans = 0;
	for (int i = 0; i < 3;++i) {
		if (S[i] == T[i])ans++;
	}
	 
	cout << ans;
}


Measured memory_bytes: 256
#include<stdio.h>

int list[1000000], p = 0;

int check(int x){
  int i;
  for (i = 0; i < p; i++){
    if(x == list[i]){
      return 1;
    }
  }
  list[p++] = x;
  return 0;
}

int main(){
  int s, count = 1;
  
  scanf("%d", &s);
  
  while(check(s) != 1){
    if(s%2 == 0){
      s /= 2;
    } else {
      s = 3*s + 1;
    }
    count++;
  }
  
  printf("%d\n", count);
  
  return 0;
}

Measured memory_bytes: 128
const input=require('fs').readFileSync('/dev/stdin','utf8').split(/[\s]/);let input_i=-1;const tn=():number=>{input_i++;return Number(input[input_i])};const tnn=(n:number):number[]=>{const a=[];for(let i=0;i<n;i++){a.push(tn())}return a};const ts=():string=>{input_i++;return String(input[input_i])};const tss=(n:number):string[]=>{const a=[];for(let i=0;i<n;i++){a.push(ts())}return a};const to=(...arg)=>{console.log(...arg)};const abs=(a)=>{return Math.abs(a)};const min=(...a)=>{return Math.min(...a)};const max=(...a)=>{return Math.max(...a)};const floor=(a)=>{return Math.floor(a)};const asc=(ar:number[])=>{return ar.sort((a,b)=>{return a-b})};const desc=(ar:number[])=>{return ar.sort((a,b)=>{return b-a})};const sw=(a,arr:any[],op:'=='|'>='|'>'|'<='|'<'='==')=>{for(let i=0;i<arr.length-1;i+=2){if(eval(a+op+arr[i])){return arr[i+1]}}return arr[arr.length-1]};const near=(n:number,arr:number[]):number=>{let ne=arr[0],ni=0;for(let i=1;i<arr.length;i++){if(Math.abs(n-ne)>Math.abs(n-arr[i])){ne=arr[i];ni=i}}return ni};const deduplicate=(a):any[]=>{return Array.from(new Set(a))};
const main=()=>{
  let [n,m]=tnn(2)
  let ar=tnn(m*2)
  let j=0,k=n
  for(let i=0;i<m*2;i+=2){
    j=max(ar[i],j)
    k=min(ar[i+1],k)
  }
  to(k-j+1<=0?0:k-j+1)
}
main()


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

using namespace std;

int main()
{
	int score, sum = 0;

	for (int i = 0; i < 5; i++)
	{
		cin >> score;

		sum += max(score, 40);
	}

	cout << sum / 5 << endl;

	return 0;
}

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

int main() {
 
  int N,sum=0,tmp;
  string n;
  int a,b;
  cin>>N>>a>>b;
  n=to_string(N);
  for(int i=1;i<=N;i++){
    if(i<10){tmp=i;if(tmp>=a&&tmp<=b){sum+=i;}}
    else if(i<100){tmp=(i%10)+(i/10);if(tmp>=a&&tmp<=b){sum+=i;}}
    else if(i<1000){tmp=(i%10)+((i%100)/10)+(i/100);if(tmp>=a&&tmp<=b){sum+=i;}}
    else if(i<10000){tmp=(i%10)+((i%100)/10)+((i%1000)/100)+(i/1000);if(tmp>=a&&tmp<=b){sum+=i;}}
    else if(i==10000&&a==1){sum+=i;}
  }
  cout<<sum<<endl;
}


Measured memory_bytes: 256
#!/usr/bin/perl

# 引数取り込み
my $a = <>;
my ( $b, $c ) = split( / /, $a );

# 処理開始
my $ans = ( $b * ( $b - 1 ) ) / 2 + ( $c * ( $c - 1 ) ) /2;
print $ans;

1;

Measured memory_bytes: 4664
#include "bits/stdc++.h"
using namespace std;
int n,d[55];
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%d",d+i);
	int sum=0;
	for(int i=0;i<n;i++)
		for(int j=i+1;j<n;j++)
			sum+=d[i]*d[j];
	printf("%d\n",sum);
}

Measured memory_bytes: 256
import heapq
n,m = map(int,input().split())
a_list=[-int(s) for s in input().split()]
heapq.heapify(a_list)

for _ in range(m):
    max_item = heapq.heappop(a_list)
    heapq.heappush(a_list,-(-max_item//2))

print(-sum(a_list))

Measured memory_bytes: 14180
import java.util.Scanner;
 
public class Main{
  public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    int num[] = new int[n];
    for(int i = 0; i < n; i++){
      num[i] = -1;
    }
    for(int i = 0; i < m; i++){
      int s = sc.nextInt()-1;
      int c = sc.nextInt();
      if((s==0&&c==0&&n!=1)||(num[s] != -1&&num[s] != c)){
        System.out.println(-1);
        return;
      } else {
        num[s] = c;
      }
    }
    int ans = 0;
    int ten = 1;
    for(int i = n-1; i >= 0; i--){   
      if(num[i]==-1){
        if(n>1&&i==0){
          num[i]=1;
        } else {
          num[i]=0;
        }
      }
      ans += num[i]*ten;
      ten*=10;
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 23764
#include<bits/stdc++.h>
#define PB push_back
#define FI first
#define SE second
#define MP make_pair
#define int long long
using namespace std;
static const int inf = 1ll<<60;
static const int MAX_N = 16777216;
typedef pair<int,int> P;

int N,D;
int X[40],Y[40];
int ans=0;
int dat[MAX_N*2];
vector<P> p1;
vector<P> p2;

class Segment{
    public :
        int n;
        void inti(int n_){
            n=1;
            while(n<n_)n*=2;
            for(int i=0;i<2*n-1;++i)dat[i]=-INT_MAX;
        }

        void update(int k,int a){
            k+=n-1;
            dat[k]=a;
            while(k>0){
                k=(k-1)/2;
                dat[k]=max(dat[k*2+1],dat[k*2+2]);
            }
        }

        int query(int a,int b,int k,int l,int r){
            if(a<=l&&r<=b)return dat[k];
            if(r<=a||b<=l)return -INT_MAX;
            else {
                int vl=query(a,b,k*2+1,l,(l+r)/2);
                int vr=query(a,b,k*2+2,(l+r)/2,r);
                return max(vl,vr);
            }
        }
};

void half(int n,int last,int x,int y,vector<P> &res) {
    if (n==last) {
        res.PB(P(x,y));
        return;
    }
    half(n-1,last,x+X[n],y+Y[n],res);
    half(n-1,last,x-X[n],y-Y[n],res);
    half(n-1,last,x,y,res);
}

signed main(){
    cin>>N>>D;
    Segment seg;
    int n2=N/2;
    for(int i=1;i<=N;++i){
        cin>>X[i]>>Y[i];
    }
    p1.reserve(MAX_N);
    half(n2,0,0,0,p1);
    p2.reserve(MAX_N);
    half(N,n2,0,0,p2);
    sort(p2.begin(),p2.end());
    seg.inti(p2.size());
    for(int i=0;i<p2.size();++i)seg.update(i,p2[i].SE);
    for(int i=0;i<p1.size();++i){
        int x=p1[i].FI+D;
        int y=p1[i].FI-D;
        int r=lower_bound(p2.begin(),p2.end(),MP(y,-inf))-p2.begin();
        int l=upper_bound(p2.begin(),p2.end(),MP(x,inf))-p2.begin();
        if(r==p2.size())continue;
        if(r>=l)continue;
        ans=max(ans,seg.query(r,l,0,0,seg.n)-p1[i].SE);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 715684
#include <iostream>
#include <vector>
using namespace std;
int main(){
    int k, n;
    cin >> k >> n;
    vector<int> A(n);
    for(int i = 0; i < n; i++) cin >> A[i];
    int max = 0;
    for(int i = 0; i < n-1; i++){
        int dist = A[i+1] - A[i];
        if(dist > max) max = dist;
    }
    int dist = k - A[n-1] + A[0];
    if(dist > max) max = dist;
    cout << k - max;
    return 0;
}

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

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

#define endl '\n'
#define ff first
#define ss second
#define int long long
#define pb push_back
#define f(i,l,r) for(ll i=l;i<=r;i++)
#define rf(i,r,l) for(ll i=r;i>=l;i--)
#define Max 5000001
#define inf 2147483647
#define llinf 9223372036854775807
#define all(v) v.begin(),v.end()
#define bp(n) __builtin_popcountll(n)
#define fast ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)

#define d0(a) cout<<a<<' ';
#define d1(a) cout<<a<<endl;
#define d2(a,b) cout<<a<<' '<<b<<endl;
#define d3(a,b,c) cout<<a<<' '<<b<<' '<<c<<endl;
#define d4(a,b,c,d) cout<<a<<' '<<b<<' '<<c<<' '<<d<<endl;
#define d5(a,b,c,d,e) cout<<a<<' '<<b<<' '<<c<<' '<<d<<' '<<e<<endl;
#define d6(a,b,c,d,e,f) cout<<a<<' '<<b<<' '<<c<<' '<<d<<' '<<e<<' '<<f<<endl;

const ll N=1e5+5,mod=1e9+7,bit=61;

void bye()
{
    cout<<"No\n";
    exit(0);
}

signed main()
{
    fast;

    ll t=1;
    //cin>>t;
    while(t--)
    {
        ll n;
        cin>>n;
        string sv[n+1];
        pll a[n+1];
        ll b=0;
        f(i,1,n)
        {
            string s;
            cin>>s;
            sv[i]=s;
            ll pref=0;
            ll sum=0;
            for(auto x:s)
            {
                sum+=(x=='('?1:-1);
                pref=min(pref,sum);
            }
            ll suff=-sum+pref;
            pref=abs(pref);
            suff=abs(suff);
            if(pref==0)  //(((()()((
            {
                a[i].ff=inf;
            }
            else if(suff==0)  //(((()()))))))
            {
                a[i].ff=-inf;
            }
            else if(pref>suff) // )))(
            {
                a[i].ff=-inf+suff;
            }
            else if(suff>pref)   // (((), ((())        i
            {
                a[i].ff=inf-pref;
            }
            else
            {
                a[i].ff=0;
            }
            a[i].ss=i;
        }
        sort(a+1,a+n+1,greater<pll>());
        b=0;
        f(i,1,n)
        {
            for(auto x:sv[a[i].ss])
            {
                b+=(x=='('?1:-1);
                if(b<0)
                {
                    bye();
                }
            }
        }
        if(b)
        {
            bye();
        }
        cout<<"Yes\n";
    }
    return 0;
}


















Measured memory_bytes: 50492
lg = []
rg = []
la = []
n, m, l = map(int, input().split())
for h in range(n):
    s = list(map(int, input().split()))
    lg.append(s)
for h in range(m):
    t = list(map(int, input().split()))
    rg.append(t)
for i in range(n):
    for j in range(l):
        p = 0
        for q in range(m):
            p = p + lg[i][q] * rg[q][j]
        # p = lg[i][k] * rg[k][j] + lg[i][k + 1] * rg[k + 1][j]
        la.append(p)
    print(" ".join(map(str, (la))))
    # print(la)
    la = []


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


vector<ll> A(200001);
vector<ll> s(200001);
int main()
{
    ll N,res=0;
    cin >> N;
    A.resize(N);s.resize(N+1);
    rep(i,0,N) cin >> A[i];
    rep(i,0,N) s[i+1] = s[i]+A[i];
    sort(s.begin(),s.end());
    ll count=0;
    rep(i,0,N){
        if(s[i] == s[i+1]){
            count++;
        }else{
            res += (count*(count+1))/2;
            count = 0;
        }
    }
    res += (count*(count+1))/2;
    cout << res << endl;
}

Measured memory_bytes: 3328
/* ****_hela**** */

#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define	endl		'\n'
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define rep(i,a,b)	for(ll int i=a;i<b;i++)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
using namespace std;

#define N  100005

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int TESTS=1;
//	cin>>TESTS;
	while(TESTS--)
	{
		int x,y,z;
		cin>>x>>y>>z;
		cout<<z<<" "<<x<<" "<<y;		
	}
	return 0;
}

Measured memory_bytes: 256
class SegTree:
    """ define what you want to do with 0 index, ex) size = tree_size, func = min or max, sta = default_value """
    
    def __init__(self,size,func,sta):
        self.n = size
        self.size = 1 << size.bit_length()
        self.func = func
        self.sta = sta
        self.tree = [sta]*(2*self.size)

    def build(self, list):
        """ set list and update tree"""
        for i,x in enumerate(list,self.size):
            self.tree[i] = x

        for i in range(self.size-1,0,-1):
            self.tree[i] = self.func(self.tree[i<<1],self.tree[i<<1 | 1])

    def set(self,i,x):
        i += self.size
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.func(self.tree[i<<1],self.tree[i<<1 | 1])

    
    def get(self,l,r):
        """ take the value of [l r) with func (min or max)"""
        l += self.size
        r += self.size
        res = self.sta

        while l < r:
            if l & 1:
                res = self.func(self.tree[l],res)
                l += 1
            if r & 1:
                res = self.func(self.tree[r-1],res)
            l >>= 1
            r >>= 1
        return res

n,k = map(int,input().split())
p = list(map(int,input().split()))

segmin = SegTree(n,min,10**18)
segmax = SegTree(n,max,-1)
segmin.build(p)
segmax.build(p)

count = [1]*n
for i in range(1,n):
    if p[i] > p[i-1]:
        count[i] = count[i-1]+1
if n == k or max(count) == n:
    print(1)
    exit()
ans = 1
check = False
if count[k-1] == k:
    check = True
for i in range(k,n):
    if count[i] >= k:
        if check:
            continue
        else:
            check = True
            ans += 1
            continue
    elif segmin.get(i-k,i+1) == p[i-k] and segmax.get(i-k,i+1) == p[i]:
        continue
    ans += 1

print(ans)
    

Measured memory_bytes: 94936
#include <bits/stdc++.h>
#define debug(x) cerr << "\n" \
                      << #x << " = " << x << ".\n"
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = ((1LL << 30) + (1LL << 29));
const ll MOD = 1000000007;
//=============================================================

int H, W;
vector<vector<int>> a;
void input()
{
  cin >> H >> W;
  a = vector<vector<int>>(H,vector<int>(W));
  rep(i, H)
  {
    rep(j, W) { cin >> a[i][j]; }
  }
}

struct MOVE{
  int x,y,xd,yd;
};
vector<MOVE> ans;

void solve()
{
  // rep(i, H)
  // {
  //   rep(j, W)
  //   {
  //     cout << a[i][j] << " ";
  //   }
  //   cout << endl;
  // }


  rep(i,H){
    rep(j,W-1){
      if (a[i][j]%2){
        ans.push_back({i+1,j+1,i+1,j+2});
        a[i][j+1]++;
      }
    }
  }
  rep(i,H-1){
    if (a[i][W-1]%2) {
      ans.push_back({i+1,W,i+2,W});
      a[i+1][W-1]++;
    }
  }

  cout<<ans.size()<<endl;
  for(auto a: ans){
    cout<<a.x<<" " << a.y<<" " << a.xd<< " " << a.yd<<endl;
  }


}


//=================================================
signed main()
{
  input();
  solve();
  return 0;
}

Measured memory_bytes: 5232
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

public class Main {

  public static void main(String[] args) {
    FastScanner sc = new FastScanner();

    long H = sc.nextLong();
    long W = sc.nextLong();

    long ans = 0;

    if (H != 1 && W != 1) {
      if (W % 2 == 0) {
        ans = H * W / 2l;
      } else {
        ans = (H * (W + 1) / 2l) - H / 2;
      }
    } else {
      ans = 1;
    }

    System.out.println(ans);

  }
}

class FastScanner {
  private final InputStream in = System.in;
  private final byte[] buffer = new byte[1024];
  private int ptr = 0;
  private int buflen = 0;

  private boolean hasNextByte() {
    if (ptr < buflen) {
      return true;
    } else {
      ptr = 0;
      try {
        buflen = in.read(buffer);
      } catch (IOException e) {
        e.printStackTrace();
      }
      if (buflen <= 0) {
        return false;
      }
    }
    return true;
  }

  private int readByte() {
    if (hasNextByte()) {
      return buffer[ptr++];
    } else {
      return -1;
    }
  }

  private static boolean isPrintableChar(int c) {
    return 33 <= c && c <= 126;
  }

  private void skipUnprintable() {
    while (hasNextByte() && !isPrintableChar(buffer[ptr])) {
      ptr++;
    }
  }

  public boolean hasNext() {
    skipUnprintable();
    return hasNextByte();
  }

  public String next() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    StringBuilder sb = new StringBuilder();
    int b = readByte();
    while (isPrintableChar(b)) {
      sb.appendCodePoint(b);
      b = readByte();
    }
    return sb.toString();
  }

  public int nextInt() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    int n = 0;
    boolean minus = false;
    int b = readByte();
    if (b == '-') {
      minus = true;
      b = readByte();
    }
    if (b < '0' || '9' < b) {
      throw new NumberFormatException();
    }
    while (true) {
      if ('0' <= b && b <= '9') {
        n *= 10;
        n += b - '0';
      } else if (b == -1 || !isPrintableChar(b)) {
        return minus ? -n : n;
      } else {
        throw new NumberFormatException();
      }
      b = readByte();
    }
  }

  public long nextLong() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    long n = 0;
    boolean minus = false;
    int b = readByte();
    if (b == '-') {
      minus = true;
      b = readByte();
    }
    if (b < '0' || '9' < b) {
      throw new NumberFormatException();
    }
    while (true) {
      if ('0' <= b && b <= '9') {
        n *= 10;
        n += b - '0';
      } else if (b == -1 || !isPrintableChar(b)) {
        return minus ? -n : n;
      } else {
        throw new NumberFormatException();
      }
      b = readByte();
    }
  }
}

Measured memory_bytes: 22740
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
using ll = long long;
int main(){
    int h, w, k, ans;
    cin >> h >> w >> k;
    ans =0;


    vector<vector<char>> c(h, vector<char>(w));
    vector<vector<char>> d(h, vector<char>(w));
    rep(i,h){
        rep(j,w){
            cin >> c[i][j];
            d[i][j]=c[i][j];
            if(c[i][j]=='#'){
            }
        }
    }

    for(int bit =0; bit < (1<<h+w); bit++){
        int sum =0;
        for(int i= 0; i< h+w; i++){
            if(bit & (1<<i)){
                if(i<h){
                    rep(j,w){
                        c[i][j]='.';
                    }
                }
                else{
                    rep(j,h){
                        c[j][i-h]='.';
                    }
                }
                }
        }
        rep(i,h){
            rep(j,w){
                if(c[i][j]=='#'){
                    sum++;
                }
                c[i][j]=d[i][j];
            }
        }
        if(sum ==k){
            ans++;
        }        
    }

    cout << ans<< endl;
}

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

#define rep(i,n) for(int i = 0; i < n; i++)
#define REP(i,n) for(int i = 1; i < n; i++)
#define sz(x) int(x.size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define endl "\n"
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
using vi = vector<int>;
using vii = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;
using vs = vector<string>;
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
const int inf = (1<<30)-1;
const ll infll = (1LL<<62)-1;
ll ceil(const ll a, const ll b){return ((a)+(b)-1)/b;}


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

  int n;
  cin >> n;
  ll ans = 0;
  REP(a,n+1) {
    REP(b,n+1) {
      REP(c,n+1) {
        ans += gcd(a, gcd(b,c));
      }
    }
  }
  cout << ans << endl;
}

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

int main() {
  int N, d = 2, flg = 1, j;
  cin >> N;
  int A[N];
  for(int i=0; i < N; i++) {
    cin >> A[i];
  };
  for(j=0; flg == 1; j++) {
    for(int i = 0; i < N; i++) {
      if(A[i] % 2 == 0) {
        A[i] /= 2;
      } else {
        flg = 0;
        break;
      };
    };
    if(flg == 0) {
      break;
    };
  };
  
  cout << j;
  return 0;
}

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

string t;

int main() {
  cin >> t;
  if (t[0] == '?') t[0] = 'D';
  if (t[t.size()-1] == '?') t[t.size()-1] = 'D';
  rep (i, t.size()-1) {
    if (t[i] == '?') {
      if (t[i+1] == '?') {
        if (t[i-1] == 'D') {
          t[i] = 'P';
        } else {
          t[i] = 'D';
        }
        continue;
      }
      if (t[i-1] == 'D' && t[i+1] == 'D') {
        t[i] = 'P';
      } else {
        t[i] = 'D';
      }
    }
  }
  cout << t << endl;
  return 0;
}


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

int main(){
	long long max = -1000000;
	long long min = 1000000;
	long long a;
	long long sum = 0;
	int n;
	cin >> n;
	for( int i = 0; i < n; i++ ){
	cin >> a;
	if(a>max) max=a;
	if(a<min) min=a; 
	sum += a;
	}
	cout << min << " " << max << " " << sum << endl;

return 0;
}

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


int main(){
  int N, K;
  int R,S,P;
  string T;

  cin >> N >> K;
  cin >> R >> S >> P;
  cin >> T;
  vector<bool> TT(N, true);
  //bool rr, ss, pp = false;
  int ans =0;

  rep(i, N){
    if(i < K){
      if(T[i] == 'r'){
        ans += P;
        //rr = true;
      }else if(T[i] == 's'){
        ans += R;
        //ss = true;
      }else{
        ans += S;
        //pp = true;
      }
    }else{
      if(T[i] == 'r'){
        if(T[i-K] != T[i] || (T[i-K] == T[i] && !TT[i-K])){
          ans += P;
          //rr =true;
        }else{
          //rr = false;
          TT[i] = false;
        }
      }else if(T[i] == 's'){
        if(T[i-K] != T[i] || (T[i-K] == T[i] && !TT[i-K])){
          ans += R;
          //ss =true;
        }else{
          //ss = false;
          TT[i] = false;
        }
      }else{
        if(T[i-K] != T[i] || (T[i-K] == T[i] && !TT[i-K])){
          ans += S;
          //pp =true;
        }else{
          //pp = false;
          TT[i] = false;
        }
      }
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 512
def merge(a, left, mid, right):
    cnt = 0
    n1 = mid - left
    n2 = right - mid
    l = a[left:left+n1]
    r = a[mid:mid+n2]
    l.append(float('inf'))
    r.append(float('inf'))
    i = 0
    j = 0
    for k in range(left, right):
        if l[i] <= r[j]:
            a[k] = l[i]
            i += 1
        else:
            a[k] = r[j]
            j += 1
            cnt += n1 - i
    return cnt


def mergeSort(a, left, right):
    if left+1 < right:
        mid = (left+right) // 2
        v1 = mergeSort(a, left, mid)
        v2 = mergeSort(a, mid, right)
        v3 = merge(a, left, mid, right)
        return v1 + v2 + v3
    else:
        return 0


n = int(input())
a = [int(v) for v in input().split()]

ans = mergeSort(a, 0, n)
print(ans)


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

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

long long MOD = 1000000000 + 7;

vector<ll> divisor(ll n){
  vector<ll> res;
  for(ll i = 1; i * i <= n; i++){
    if(n % i == 0){
      res.push_back(i);
      if(i != n / i) res.push_back(n / i);
    }
  }
  return res;
}

int main(){
  cout << setprecision(10);
  ll N; cin >> N;

  ll ans = 0;

  // KがNの約数のとき、割り切った後、N%K==1ならOK
  auto list = divisor(N);
  for(auto x: list){
    if(x==1) continue;
    ll n = N;
    while(n%x==0 && n >= 1){
      // cerr << "n: " << n << " x: " << x << endl;
      n/=x;
    }

    if(n%x==1) ans++;
  }

  // KがNの約数でないとき、N%K==1ならOK
  auto list2 = divisor(N-1);
  // 1以外
  ans += list2.size() - 1;

  cout << ans << endl;
   
}


Measured memory_bytes: 3708
N,M = [int(x) for x in str(input()).split()]
E=[]
for i in range(M):
  E.append([int(x) for x in str(input()).split()])


def dfs(u):
  visited[u]=True
  for j in adj[u]:
    if visited[j]==False:
      dfs(j)

count=0
for i in range(M):
  P=E[:i]+E[i+1:]
  visited=[False for x in range(0,N+1)]
  adj=[[0] for k in range(0,N+1)]
  for j in range(1,N+1):
    r=[]
    for l in P:
      if l[0]==j:
        r.append(l[1])
      elif l[1]==j:
        r.append(l[0])
    adj[j]=r
  dfs(1)
  if sum(visited)!=N:
    count+=1
print(count)

Measured memory_bytes: 3064
n=int(input())
dp=[[0 for i in range(3)] for i in range(n)]
dp[0]=list(map(int,input().split()))
for i in range(1,n):
    S=list(map(int,input().split()))
    for j in range(3):
        dp[i][j]=max(dp[i-1][j-1],dp[i-1][j-2])+S[j]

print(max(dp[n-1]))
#dp[i][j]=i番目にjを選んだ時の最大値(jはa,b,cに対応している。)

Measured memory_bytes: 87760
#include <iostream>
#include <algorithm>
#include <climits>
#include <numeric>
#include <iomanip>
#include <cmath>
#include <vector>
#include <set>
#include <unordered_set>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <unordered_map>
 
#define barsik ios::sync_with_stdio(false)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
typedef long long ll;
typedef std::vector<int> vi;
typedef std::pair <int, int> pii;
typedef std::unordered_set <int> u_si;
const double PI = acos(-1);
const long double EPS = 1e-9;
using namespace std;

void solve(){
    string s;
    cin >> s;
    if(s == "SUN") cout << 7;
    if(s == "MON") cout << 6;
    if(s == "TUE") cout << 5;
    if(s == "WED") cout << 4;
    if(s == "THU") cout << 3;
    if(s == "FRI") cout << 2;
    if(s == "SAT") cout << 1;
}

int main(){
    int q = 1;
    //cin >> q;
    while(q--) solve();
}
// vse dolzhny vyiti v internet po hhtp


Measured memory_bytes: 256
package main

import "fmt"

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func main() {
	var (
		n int
		s string
	)
	fmt.Scan(&n, &s)

	ans := 0
	for i := 1; i < n; i++ {
		lm := make(map[rune]bool)
		for _, r := range s[:i] {
			lm[r] = true
		}

		rm := make(map[rune]bool)
		for _, r := range s[i:] {
			if _, ok := lm[r]; ok {
				rm[r] = true
			}
		}
		if v := len(rm); v > ans {
			ans = v
		}
	}

	fmt.Println(ans)
}


Measured memory_bytes: 512
#include <stdio.h>
int main(){
	int x[10000],y[10000],a,b,i,j;
	while(1){
		scanf("%d %d",&a,&b);
		if(a==0 && b==0)
			break;
		x[i]=a;
		y[i]=b;
		i++;
	}
	for(j=0;j<i;j++){
		if(x[j]>y[j])
			printf("%d %d\n",y[j],x[j]);
		else
			printf("%d %d\n",x[j],y[j]);
	}
	return 0;
}

Measured memory_bytes: 624
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int(i)=0;i<(n);i++)
typedef long long ll;

int main(){
  ll hh,ww,ans=1e11,s[3];cin>>hh>>ww;
  REP(k,2){
    ll h=hh,w=ww;
    if(k) swap(h,w);
    for(ll i=1;i<w;i++){
      s[0]=h*i;
      if(!(h%2)||!((w-i)%2)) s[1]=s[2]=h*(w-i)/2;
      else{
        s[1]=min(h,w-i)*(max(h,w-i)/2);
        s[2]=h*w-s[0]-s[1];
      }
      ans=min(ans,max({s[0],s[1],s[2]})-min({s[0],s[1],s[2]}));
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
extern crate core;

use std::fmt;
use std::cmp::{max, min};
macro_rules! read_line{
    () => {{
        let mut line = String::new();
        std::io::stdin().read_line(&mut line).ok();
        line
    }};
    (delimiter: ' ') => {
        read_line!().split_whitespace().map(|x|x.to_string()).collect::<Vec<_>>()
    };
    (delimiter: $p:expr) => {
        read_line!().split($p).map(|x|x.to_string()).collect::<Vec<_>>()
    };
    (' ') => {
        read_line!(delimiter: ' ')
    };
    ($delimiter:expr) => {
        read_line!(delimiter: $delimiter)
    };
    (' '; $ty:ty) => {
        read_line!().split_whitespace().map(|x|x.parse::<$ty>().ok().unwrap()).collect::<Vec<$ty>>()
    };
    ($delimiter:expr; $ty:ty) => {
        read_line!($delimiter).into_iter().map(|x|x.parse::<$ty>().ok().unwrap()).collect::<Vec<$ty>>()
    };
}
macro_rules! let_all {
    ($($n:ident:$t:ty),*) => {
        let line = read_line!(delimiter: ' ');
        let mut iter = line.iter();
        $(let $n:$t = iter.next().unwrap().parse().ok().unwrap();)*
    };
}
fn can_make_one(count_zero: i32, count_one: i32) -> bool {
    count_zero % 2 == 0 || count_one != 0
}
fn print_zero(count_zero: i32, count_one: i32) {
    for _ in 0 .. count_zero / 2 {
        println!("0\n0");
    }
    if count_one > 0 {
        println!("1")
    }
    if count_zero % 2 == 1 {
        println!("0")
    }
    for _ in 1 .. count_one {
        println!("1")
    }
}
fn print_zero_with_void(void: i32, count_zero: i32) {
    for _ in 0 .. count_zero / 2 {
        println!("0\n0");
    }
    println!("{}", void);
    println!("0");
}
fn main() {
    let_all!(n: usize);
    let mut count_zero = 0;
    let mut count_one = 0;
    let mut others = Vec::<i32>::new();
    for _ in 0 .. n {
        let_all!(a: i32);
        match a {
            0 => count_zero += 1,
            1 => count_one += 1,
            _ => others.push(a),
        }
    }
    others.sort();
    if can_make_one(count_zero, count_one) {
        if others.len() > 1 && others[others.len() - 1] == 3 && others[others.len() - 2] == 2 {
            for _ in 2 .. others.len() {
                println!("2");
            }
            println!("3\n2");
        }else {
            for &o in &others {
                println!("{}", o);
            }
        }
        print_zero(count_zero, count_one);
    }else {
        if others.len() > 2 && others[others.len() - 1] == 3 && others[others.len() - 2] == 2 {
            for _ in 3 .. others.len() {
                println!("2");
            }
            println!("3\n2");
        }else {
            for i in 1..others.len() {
                println!("{}", others[i]);
            }
        }
        if let Some(&i) = others.first() {
            print_zero_with_void(i, count_zero);
        }else {
            for _ in 0..count_zero {
                println!("0")
            }
        }
    }
}


Measured memory_bytes: 5048
#include<iostream>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
#include<stack>
#include<cstring>
#include<stdio.h>
using namespace std;

int main(){
  stack<int> st;
  string str;
  int a, b;
  while(cin>>str){
    if(str=="+"){
      a = st.top(); st.pop();
      b = st.top(); st.pop();
      st.push(a + b);
    }
    else if(str=="-"){
      a = st.top(); st.pop();
      b = st.top(); st.pop();
      st.push(b - a);
    }
    else if(str=="*"){
      a = st.top(); st.pop();
      b = st.top(); st.pop();
      st.push(a * b);
    }
    else st.push(atoi(str.c_str()));
    if(getchar() == '\n'){
      cout<<st.top()<<endl;
      return 0;
    }
  }
}



Measured memory_bytes: 3176
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

#define type std::string

char solve(std::string a, std::string b, std::string c){

  char current = a[0];
  int A, B, C;
  A = a.size();
  B = b.size();
  C = c.size();

  int ai = 1, bi = 0, ci = 0;

  while(ai != A+1 && bi != B+1 && ci != C+1){
    if(current == 'a'){
      current = a[ai];
      ai++;
    }
    if(current == 'b'){
      current = b[bi];
      bi++;
    }
    if(current == 'c'){
      current = c[ci];
      ci++;
    }
  }  

  if(ai == A+1){
    current = 'A';
    ai++;
  }
  if(bi == B+1){
    current = 'B';
    bi++;
  }
  if(ci == C+1){
    current = 'C';
    ci++;
  }

  return current;
}

int main(){

  std::string a, b, c;

  getline(std::cin, a);
  //std::cin.ignore();
  getline(std::cin, b);
  //std::cin.ignore();
  getline(std::cin, c);

  char result = solve(a, b, c);

  std::cout << result << std::endl;
  
  return 0;
}


Measured memory_bytes: 256
/*input
10
1
10
100
1000000007
10000000000
1000000009
999999999
999
999
999
*/
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define F first
#define S second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define pb push_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
	out<<'('<<P.F<<','<<P.S<<')';
	return out;
}

//}}}
const ll maxn=100005;
const ll maxlg=__lg(maxn)+2;
const ll INF64=8000000000000000000LL;
const int INF=0x3f3f3f3f;
const ll MOD=ll(1e9+7);
const double PI=acos(-1);
//const ll p=880301;
//const ll P=31;

ll mypow(ll a,ll b){
	ll res=1LL;
	while(b){
		if(b&1) res=res*a%MOD;
		a=a*a%MOD;
		
		b>>=1;
	}
	return res;
}

vector<ll> p;
bool isp[maxn];

ll a[maxn];

map<ll,ll> pr;

map<ll,ll> mp;
ll nocube(ll x){
	__int128 cc=1;
	ll meow=x;
	for(ll i:p){
		int cnt=0;
		while(x%i==0){
			cnt++;
			x/=i;
			meow/=i;
			// cout<<i<<' '<<meow<<' '<<x<<'\n';
		}
		REP(j,cnt%3) x*=i;
		if(cnt%3==1) cc*=i*i;
		else if(cnt%3==2) cc*=i;
	}
	// cout<<(ll)cc<<' '<<meow<<'\n';
	if(mp.count(meow)) cc*=mp[meow];
	else cc*=meow*meow;
	if(cc>1e10) cc=-1;
	pr[x]=cc;
	// cout<<x<<' '<<pr[x]<<'\n';
	return x;
}

map<ll,ll> cnt;

const int magic=2154;

set<ll> vis;

int main()
{
	IOS;

	for(int i=2;i<magic;i++){
		if(!isp[i]){
			p.pb(i);
		}
		for(int j=0;i*p[j]<magic;j++){
			isp[i*p[j]]=1;
			if(i%p[j]==0) break;
		}
	}

	for(ll i=1;i<100000;i++){
		mp[i*i]=i;
	}

	int n;
	cin>>n;
	REP(i,n) cin>>a[i];
	// REP(i,n) a[i]=999999967LL-i;
  	REP(i,n) a[i]=nocube(a[i]);
	// REP(i,n) cout<<a[i]<<" \n"[i==n-1];
	bool flag=0;
	REP(i,n){
		if(a[i]>1) cnt[a[i]]++;
		else flag=1;
	}
	ll ans=0;
	for(auto i:cnt){
		ll type=i.F;
		if(vis.count(type)) continue;

		ll tmp=pr[type];

		
		if(tmp<10000000005LL&&cnt.count((ll)tmp)){
			ans+=max(i.S,cnt[tmp]);
			vis.insert(tmp);
		}
		else ans+=i.S;
	}
	cout<<ans+flag<<'\n';
	return 0;
}


Measured memory_bytes: 19840
A, B, C, X = [int(input()) for i in range(4)]
count = 0
for i in range(0, A+1):
    for k in range(0, B+1):
        for l in range(0, C+1):
            if 500*i + 100*k + 50*l == X:
                count += 1
print(count)

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <cstdlib>

template<class T> inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

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

const long long INF {1LL << 60};
const int max_index {100010};


int main()
{
  // input 
  long long h [max_index];
  int n {0};
  std::cin >> n;
  for ( int i = 0; i < n; i++ ) {
    std::cin >> h[i];
  }

  // initialize dp table
  long long dp [max_index];
  for ( int i = 0; i < n; i++ ) {
    dp[i] = INF;
  }
  dp[0] = 0;

  for ( int i = 1; i < n; i++ ) {
    chmin(dp[i], dp[i-1] + std::abs(h[i] - h[i - 1]));
    if ( i > 1 ) {
      chmin(dp[i], dp[i-2] + std::abs(h[i] - h[i-2]));
    }
  }
  
  // answer
  std::cout << dp[n-1] << std::endl;
  return 0;
}

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

using namespace std;

int solve(int N, int cnt) {
    if (N < 10) return cnt;
    cnt++;
    if (cnt == 10000000) return -1;
    int syou, amari;
    int mn = -1;
    for (int i = 10; i < 10000000; i *= 10) {
        syou = N / i;
        if (!syou) break;
        amari = N % i;
        mn    = max(mn, syou * amari);
    }
    cnt = solve(mn, cnt);
    return cnt;
}

int main() {
    int Q;
    cin >> Q;
    int N;
    vector<int> ans;
    for (int i = 0; i < Q; i++) {
        cin >> N;
        int cnt = 0;
        ans.push_back(solve(N, cnt));
    }
    for (int i : ans) cout << i << endl;
}


Measured memory_bytes: 3164
#include <bits/stdc++.h>
using namespace std;
long long dp[1002][1002];
int main() {
  int n;cin>>n;
  for(int i=0; i<n; i++){
  
  string a,b; cin>>a>>b;
  int al=a.size(); int bl=b.size();
  for (int i=0;i<1002;i++){for(int j=0;j<1002;j++){dp[i][j]=0;}}
  for (int j=0;j<al;j++){
  for (int k=0;k<bl;k++){
  if(a[j]==b[k]){dp[j+1][k+1]=dp[j][k]+1;}
  else{dp[j+1][k+1]=max(dp[j+1][k],dp[j][k+1]);}
  }
  }
  cout << dp[al][bl] << endl;
  }
}	


Measured memory_bytes: 11048
program xor_partitioning
  implicit none
  integer(8), parameter :: md = 1000000007_8
  integer, parameter :: p = 1048575
  integer :: n, a(500000) = 0, x(0:500000) = 0, m, i, k
  integer(8) :: ans = 0_8, dp0(0:p) = 1_8, dpx(0:p) = 0_8, dpz(0:p) = 0_8
  integer(8) :: prev0, prevx, next0, nextx
  read(*,*) n
  read(*,*) a(1:n)
  do i = 1, n
    x(i) = xor(x(i-1),a(i))
  end do
  if (x(n) == 0) then
    m = 1
    do i = 0, n-1
      if (x(i) == 0) then
        m = m+1
        cycle
      end if
      k = m-dpz(x(i))
      dp0(x(i)) = mod(dp0(x(i))+int(k,8)*dpx(x(i)),md)
      dpx(x(i)) = mod(dpx(x(i))+dp0(x(i)),md)
      dpz(x(i)) = int(m,8)
    end do
    ans = pow(2_8,m-2)
    do i = 0, p
      ans = mod(ans+dpx(i),md)
    end do
    write(*,'(i0)') ans
    stop
  end if
  prev0 = 1_8
  prevx = 0_8
  do i = 1, n
    next0 = prev0
    nextx = prevx
    if (x(i) == 0) next0 = mod(prev0+prevx,md)
    if (x(i) == x(n)) nextx = mod(prev0+prevx,md)
    prev0 = next0
    prevx = nextx
  end do
  write(*,'(i0)') prev0
contains
  integer(8) function pow(x,n)
    integer(8), intent(in) :: x
    integer, intent(in) :: n
    integer :: m
    integer(8) :: p
    pow = 1_8
    p = x
    m = n
    do while (m > 0)
      if (btest(m,0)) pow = mod(pow*p,md)
      p = mod(p*p,md)
      m = rshift(m,1)
    end do
  end
end program xor_partitioning

Measured memory_bytes: 29312
#include<algorithm>
#include<iomanip>
#include<iostream>
#include<queue>
#include<string>
#include<unordered_set>
#include<vector>
using namespace std;
typedef long long ll;
const ll INF = 1000000000000000000;

ll N, ans;
ll cnt[20][20];

ll get_first_digit(ll x){
    while(true){
        if(x < 10){
            return x;
        }else{
            x /= 10;
        }
    }
}

int main(){
    cin >> N;
    for(int i=1; i<=N; i++){
        ll fd = get_first_digit(i);
        ll ld = i % 10;
        cnt[fd][ld]++;
    }
    for(int i=1; i<10; i++){
        for(int j=1; j<10; j++){
            ans += cnt[i][j] * cnt[j][i];
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256