akhauriyash/Code-Regression huggingface dataset:
#168 - F
import sys
import numpy as np
#from numba import njit


def main():
    N, M = map(int, sys.stdin.buffer.readline().split())
    LineData = np.int64(sys.stdin.buffer.read().split())

    INF = 10**9 + 1

    LineData = LineData.reshape(-1, 3)
    A, B, C = LineData[:N].T
    D, E, F = LineData[N:].T
    #X = np.unique(np.concatenate([D, [-INF, 0, INF]]))
    #Y = np.unique(np.concatenate([C, [-INF, 0, INF]]))
    X = np.unique(np.concatenate([D, [-INF, INF]]))
    Y = np.unique(np.concatenate([C, [-INF, INF]]))
    A = np.searchsorted(X, A)
    B = np.searchsorted(X, B, 'right') - 1
    C = np.searchsorted(Y, C)
    D = np.searchsorted(X, D)
    E = np.searchsorted(Y, E)
    F = np.searchsorted(Y, F, 'right') - 1

    area = cal_area(A, B, C, D, E, F, X, Y)

    if area == 0:
        print("INF")
    else:
        print(area)


#@njit
def cal_area(A, B, C, D, E, F, X, Y):
    x = np.searchsorted(X, 0, 'right') - 1
    y = np.searchsorted(Y, 0, 'right') - 1

    DX = X[1:] - X[:-1]
    DY = Y[1:] - Y[:-1]

    A = A.tolist()
    B = B.tolist()
    C = C.tolist()
    D = D.tolist()
    E = E.tolist()
    F = F.tolist()
    X = X.tolist()
    Y = Y.tolist()
    DX = DX.tolist()
    DY = DY.tolist()

    LenX = len(X)
    LenY = len(Y)

    visit = [[False] * LenY for _ in range(LenX)]
    visit[x][y] = True
    area = 0
    queue = [(x, y)]

    LineX = [[False] * LenY for _ in range(LenX)]
    LineY = [[False] * LenY for _ in range(LenX)]

    #for x1, x2, y in zip(A, B, C):
    #    for x in range(x1, x2):
    #        LineY[x][y] = True
    for i in range(len(A)):
        y = C[i]
        for x in range(A[i], B[i]):
            LineY[x][y] = True

    #for x, y1, y2 in zip(D, E, F):
    #    for y in range(y1, y2):
    #        LineX[x][y] = True
    for i in range(len(D)):
        x = D[i]
        for y in range(E[i], F[i]):
            LineX[x][y] = True

    LenX -= 1
    LenY -= 1
    
    while queue:
        x, y = queue.pop()

        if x == 0 or x == LenX or y == 0 or y == LenY:
            area = 0
            break
        
        area += DX[x] * DY[y]

        if not LineX[x][y] and not visit[x - 1][y]:
            visit[x - 1][y] = True
            queue.append((x - 1, y))
        if not LineY[x][y] and not visit[x][y - 1]:
            visit[x][y - 1] = True
            queue.append((x, y - 1))
        if not LineX[x + 1][y] and not visit[x + 1][y]:
            visit[x + 1][y] = True
            queue.append((x + 1, y))
        if not LineY[x][y + 1] and not visit[x][y + 1]:
            visit[x][y + 1] = True
            queue.append((x, y + 1))

    return area


if __name__ == '__main__':
	main()

sys.exit()


Measured memory_bytes: 66260
N = int(input())
A = [int(i) for i in input().split()]

M = max(A)
m = M
a = 1
while m // 2 != 0:
  m = m//2
  a += 1
#aはMの桁数

b = 0
for i in range(a):
  c = 0
  for j in range(N):
    c += (A[j] & 2**i)//(2**i)  #A[j]の2**iの位の値をcに加えている
  b = (b + c*(N-c)*pow(2,i,10**9+7)) % (10**9+7)
  
print(b)

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

using namespace std;

const long long INF = 1e18;
const int N = 1e5;
const int MOD = 1e9 + 7;

const double PI = acos(-1);


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int x, y;
    cin >> x >> y;
    int ans = 0;
    if (x == 1)
        ans += 300000;
    if (x == 2)
        ans += 200000;
    if (x == 3)
        ans += 100000;
    if (y == 1)
        ans += 300000;
    if (y == 2)
        ans += 200000;
    if (y == 3)
        ans += 100000;
    if (x == y && x == 1)
        ans += 400000;
    cout << ans;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main() {
	int a;
	int c = 0;
	string b;
	cin >> a >> b;
	for (int i = 0; i < (int)b.size(); ++i) {
		if (i == a) {
			cout << "..." << endl;
			c++;
			break;
		}
		char ch = b[i];
		cout << ch;
	}
	if (c == 0)cout << endl;
}

Measured memory_bytes: 3132
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define loops(i, s, n) for (ll i = s; i < n; i++)
#define loop(i, n) for (ll i = 0; i < n; i++)
#define eps 1e-9
#define loopitr(mp) for (auto itr = mp.begin(); itr != mp.end(); itr++)
#define init(arr, n, val)       \
    for (ll i = 0; i < n; i++) \
        arr[i] = val;
#define even_set 0xAAAAAAAA ... 1010101010
#define odd_set 0x55555555 ... 01010101
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
#define vall(v) v.begin(), v.end()
#define mkp make_pair
#define ret return
#define cont continue
#define nl endl
#define ff first
#define ss second
#define cnt_bits __builtin_popcount
#define init(arr, n, val)       \
    for (ll i = 0; i < n; i++) \
        arr[i] = val;
const ll mod = 1000000007;
ll dp[3001][3001];

ll sum(ll i, ll j, ll ps[]){
    ret ps[j] - ((i-1>=0) ? ps[i-1] : 0);
}

int main()
{

    fastio;
    ll n, k;
    cin >> n;
    ll arr[n];
    ll ps[n];
    for (ll &x : arr)
    {
        cin >> x;
    }

    for (ll i = 0; i < n; i++)
    {
        dp[i][i] = arr[i];
        ps[i] = arr[i] + ((i - 1 >= 0) ? ps[i - 1] : 0);
    }

    for (ll len = 2; len <= n; len++)
    {
        for (ll i = 0; i <= n - len; i++)
        {
            ll j = i + len - 1;
            
            if (len == 2)
            {
                dp[i][j] = max(arr[i], arr[j]);
            }
            else
            {
                dp[i][j] = max(arr[i] + sum(i+1, j, ps) - dp[i + 1][j] , arr[j] + sum(i, j-1, ps) - dp[i][j - 1]);
            }
        }
    }

    cout << 2*dp[0][n - 1] - ps[n-1] << endl;
}

Measured memory_bytes: 70016
import math
x = int(input())

if x<=6:
    print(1)
elif x<=11:
    print(2)
else:
    ans = (x//11)*2
    res = (x%11)
    if res==0:
        res =0
    elif res<=6:
        res = 1
    elif res<=11:
        res = 2
    print(ans+res)


Measured memory_bytes: 9056
#include <stdio.h>
typedef unsigned long long llu;

const llu mod = (llu)(1e9) + 7;
llu n;
llu fact[1005];

int main()
{
	llu ans = 1;
	
	scanf("%llu", &n);

	for (llu i = 2; i <= n; i++) {
		llu m = i;
		llu j = 2;

		while (m > 1) {
			if (m % j == 0) {
				fact[j]++;
				m /= j;
			} else {
				j++;
			}
		}
	}

	for (llu i = 1; i <= n; i++) {
		ans *= (fact[i] + 1); 
		ans %= mod;
	}

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

	return 0;
}


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

// as + bt = GCD(a,b) a,b:const s,t:var(any)
// return GCD(a,b)
long long extGCD(long long a, long long b, long long& s,
                 long long& t) {
    s = 1, t = 0;
    while(b) {
        long long tmp = a / b;
        a -= b * tmp;
        s -= t * tmp;
        swap(a, b);
        swap(s, t);
    }
    return a;
}

// x≡b_i(mod m_i) calc min x,lcm(m_i).
// if not exist, return (-1,-1)
pair<long long, long long> ChineseRem(
        const vector<long long>& b,
        const vector<long long>& m) {
    long long r = 0, lcm = 1;
    assert(b.size() == m.size());
    long long bsize = b.size();
    for(int i = 0; i < bsize; ++i) {
        long long p, q, d, now;
        d = extGCD(lcm, m[i], p, q);
        if((b[i] - r) % d != 0) return make_pair(-1, -1);
        now = (b[i] - r) / d * p % (m[i] / d);
        r += lcm * now;
        lcm *= m[i] / d;
    }
    return make_pair((r + lcm) % lcm, lcm);
}

long long n;
vector<long long> p,q,fmemo,lmemo;

long long solve();

int main(){
    cin >> n;
    p.resize(n);
    q.resize(n);
    fmemo.assign(n,0);
    lmemo.assign(n,0);
    for(int i = 0;i < n;++i){
        cin >> p[i];
        --p[i];
    }
    for(int i = 0;i < n;++i){
        cin >> q[i];
        --q[i];
    }
    cout << solve() << endl;
    return 0;
}

long long solve(){
    // prepair
    for(int i = 0;i < n;++i){
        long long now = p[i];
        bool ch = 0;
        for(int j = 0;j < n;++j){
            if(now == i){
                fmemo[i] = j;
                ch = 1;
            }
            now = q[now];
            if(now == p[i]){
                lmemo[i] = j + 1;
                break;
            }
        }
        if(!ch)return -1;
    }
    long long ans = 0;
    return ChineseRem(fmemo,lmemo).first;
}


Measured memory_bytes: 3112
package main

import (
	"fmt"
	"sort"
)

type Shop struct {
	price int
	max   int
}

type Shops []Shop

func (s Shops) Len() int {
	return len(s)
}

func (s Shops) Swap(i, j int) {
	s[i], s[j] = s[j], s[i]
}

func (s Shops) Less(i, j int) bool {
	return s[i].price < s[j].price
}

func main() {
	var n, m, sum int
	fmt.Scan(&n, &m)

	shops := make(Shops, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&shops[i].price, &shops[i].max)
	}
	sort.Sort(shops)

	for _, s := range shops {
		if s.max <= m {
			m -= s.max
			sum += s.price * s.max
		} else {
			sum += s.price * m
			break
		}
	}

	fmt.Println(sum)
}


Measured memory_bytes: 6912
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double

const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;
const int mod=1000000007;

int main(){
	int n,a[3][101001]={};
	LL c=0;
	cin>>n;
	FOR(j,0,3)FOR(i,0,n)cin>>a[j][i];
	FOR(i,0,3){
		sort(a[i],a[i]+n);
	}
	FOR(i,0,n){
		int t=a[1][i];
		int av=lower_bound(a[0],a[0]+n,t)-a[0];
		int be=n-(upper_bound(a[2],a[2]+n,t)-a[2]);
		//cout<<i<< " "<<t<<" "<<av<<" "<<be<<endl;
		c+=1LL*av*be;
	}

	cout<<c<<endl;
    return 0;
}


Measured memory_bytes: 1408
import java.util.*;

public class Main{
	static int search(int[] l,int n,int key){
		for(int i = 0; i < n; i++){
		    if(l[i] == key){
					return i;
				}
		}
		return -1 ;
	}

	public static void main(String[] args){
	    Scanner scanner = new Scanner(System.in);

	    int n = scanner.nextInt();
	    int[] l = new int[n+1];
	    for(int i = 0; i < n; i++){
				l[i] = scanner.nextInt();
			}

	    int q = scanner.nextInt();
	    int sum = 0;

	    for(int i = 0; i < q; i++){
	        if(search(l,n+1,scanner.nextInt())>=0){
						sum++;
	    	}
			}

	    System.out.println(sum);
	}
}



Measured memory_bytes: 39944
#include <bits/stdc++.h>
//debug
#define vecprint(v) rep(i,v.size())cout << v[i] << " ";cout << endl;
#define setprint(s) for(auto i=s.begin();i!=s.end();i++)cout << *i << " ";cout << endl;
#define mappairprint(s) for(auto i=s.begin();i!=s.end();i++)cout << i->first << " " << i->second << endl;cout << endl;
//reader
#define r1(a) cin>>(a)
#define r2(a,b) cin>>(a)>>(b)
#define r3(a,b,c) cin>>(a)>>(b)>>(c)
//writer
#define w1(a) cout<<(a)<<" "
#define w2(a,b) cout<<(a)<<" "<<(b)<<" "
#define w3(a,b,c) cout<<(a)<<" "<<(b)<<" "<<(c)<<" "
#define wl1(a) cout<<(a)<<endl
#define wl2(a,b) cout<<(a)<<" "<<(b)<<endl
#define wl3(a,b,c) cout<<(a)<<" "<<(b)<<" "<<(c)<<endl
//variable definition
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
//roop
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rep1(i,n) for (int i = 1; i <= (n); ++i)
#define all(c) c.begin(),c.end()
//term
#define elif else if
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
using namespace std;
using ll = long long;
//const
constexpr double PI = 3.141592653589793238462643383279;
vector<int> dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};


int main() {
  //input
  int n;
  cin >> n;
  
  map<int, int> m;
  
  //process
  int ret = 0;
  int max = 10000;
  rep1(x,max) {
    for(int y=x; y<max; y++) {
      if(pow(x+y,2)/2 > n) break;
      for(int z=y; z<max; z++) {
        int tmp = (pow(x+y,2) + pow(y+z,2) + pow(x+z,2)) / 2;
        //cout << x << " " << y << " " << z << " " << tmp << endl;//dbg
        
        if(tmp > n) break;
        if(x == y && y ==z) m[tmp]++;
        else if((x == y && y !=z) || (y == z && x !=y) || (x == z && x !=y)) m[tmp]+=3;
        else m[tmp]+=6;
      }
    }
  }

  //output
  rep1(i,n) cout << m[i] << endl;
}

Measured memory_bytes: 4068
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,i,c=0,flag=0;
    float p=0,sum=0,m;
    cin>>n>>m;
    int a[n+2];
    for(i=0; i<n; i++)
    {
        cin>>a[i];

        sum=sum+a[i];
    }
    p=4.0*m;
    p=(1/p)*sum;
    //cout<<sum<<" "<<p<<endl;
    sort(a,a+n);
    for(i=n-1; i>=0; i--)
    {
        if(a[i]>=p)
        {
            c++;
        if(c==m)
        {
            flag=1;
            break;

        }
        else
        {
            flag=0;

        }
        }

    }
    if(flag==1)
    {cout<<"Yes"<<endl;

    }
    else
    {cout<<"No"<<endl;}





}


Measured memory_bytes: 384
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <vector>

using namespace std;

int main() {
  int A, B, C, X, Y;

  cin >> A >> B >> C >> X >> Y;

  const size_t naive = A * X + B * Y;
  const size_t cand1 =
      X < Y ? C * 2 * X + (Y - X) * B : C * 2 * Y + (X - Y) * A;

  const auto ans = min({naive, cand1, static_cast<size_t>(C * 2 * max(X, Y))});
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <array>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;
using ll = long long;
using pint = pair<int, int>;
using pll = pair<ll, ll>;

constexpr double EPS = 1e-7;
constexpr int INF = 1e9;
constexpr ll LINF = 1e18;
#define PI (acos(-1))

constexpr int MOD = 1e9 + 7;

vector<int> a;
vector<int> ah;

int gcd(int a, int b) {
	if (a < b) {
		return gcd(b, a);
	}

	int r = a % b;
	while (r != 0) {
		a = b;
		b = r;
		r = a % b;
	}
	return b;
}

ll lcm(ll x, ll y) {
	return (x * y) / gcd(x, y);
}

ll nlcm(vector<int> &nums) {
	ll l = nums[0];
	for (int i = 1; i < nums.size(); i++) {
		l = lcm(l, nums[i]);
	}
	return l;
}

int main(int argc, char const *argv[]) {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);

	ll N, M;
	cin >> N >> M;
	a.resize(N);
	ah.resize(N);

	for (int i = 0; i < N; i++) {
		cin >> a[i];
		ah[i] = a[i] / 2;
	}

	ll l = nlcm(ah);
	for (int i = 0; i < N; i++) {
		if (l % a[i] == 0) {
			cout << 0 << endl;
			return 0;
		}
	}

	cout << (M / l + 1) / 2 << endl;

	return 0;
}


Measured memory_bytes: 1024
X,Y,Z,K = map(int,input().split())
alist = list(map(int,input().split()))
blist = list(map(int,input().split()))
clist = list(map(int,input().split()))

alist.sort(reverse=True)
blist.sort(reverse=True)
clist.sort(reverse=True)

ablist = []
for i in alist:
  for j in blist:
      ablist.append(i+j)
      
ablist.sort(reverse=True)
ablist = ablist[0:K]

abclist = []
for ij in ablist:
  for k in clist:
    abclist.append(ij+k)
    
abclist.sort(reverse=True)
for ijk in range(K):
  print(abclist[ijk])

Measured memory_bytes: 155196
#include<iostream>
#include<vector>
#include<numeric>

using namespace std;

int main() 
{
    constexpr int kinf=100001;
    int N,K;
    cin>>N;

    vector<int>B;
    for (int i = 0; i < N-1; i++)
    {
        int b;
        cin>>b;
        B.push_back(b);
    }
    B.push_back(kinf);

    vector<int>A(N);
    A[0]=B[0];

    for (int i = 1; i < N; i++)
    {
        A[i]=min(B[i-1],B[i]);
    }

    int ans =accumulate(A.begin(),A.end(),0);
    cout<<ans<<endl;
    return 0;
}

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

struct edge {
  int from;
  int to;
  int len;
};

int main() {
  int l;
  cin >> l;
  int r = 0;
  for ( int i = 1; i*2 <= l; i*=2 ) { r++; }
  int r2 = 1 << r;
  if ( r > 19 ) { r = 19; }

  int n = r+1;
  vector<edge> es;
  for ( int i = 1; i < n; i++ ) {
    edge t;
    t.from = i;
    t.to = i+1;
    t.len = 0;
    es.push_back(t);
    t.len = 1 << (i-1);
    es.push_back(t);
  }

  for ( int i = n-1; i >= 1; i-- ) {
    int s = l - (1 << (i-1));
    if ( s < r2 ) { continue; }
    edge t;
    t.from = i;
    t.to = n;
    t.len = s;
    es.push_back(t);
    l = s;
  }


  cout << n << ' ' << es.size() << endl;
  for ( int k = 0; k < es.size(); k++ ) {
    cout << es[k].from << ' ' << es[k].to << ' ' << es[k].len << endl;
  } 
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>


int main() {
	int N;
	int V[20], C[20] = { 0 };
	int total[20];
	int sum = 0;
	int i;

	scanf("%d", &N);

	for (i = 0; i < N; i++) {
		scanf("%d", &V[i]);

	}

	for (i = 0; i < N; i++) {
		scanf("%d", &C[i]);
	}

	for (i = 0; i < N; i++) {
		total[i] = V[i] - C[i];
		if (total[i] > 0) {
			sum = sum + total[i];
		}
	}
	printf("%d\n", sum);
	return 0;


}

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




int main() {
	string s;
	cin >> s;
	
	for(int i = 0; i < s.size(); i++) {
		if(i%2 == 0) {
			if(s[i] == 'R' || s[i] == 'U' || s[i] == 'D') continue;
			else {cout << "No" << endl; return 0;}
		}
		else{
			if(s[i] == 'L' || s[i] == 'U' || s[i] == 'D') continue;
			else {cout << "No" << endl; return 0;}
		}
	}
	cout << "Yes" << endl; return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    if(c>b||d<a)
        cout<<"0"<<endl;
    else if(a<=c&&a<=d&&c<=b&&b<=d)
        cout<<b-c<<endl;
    else if(c<=a&&c<=b&&d>=b&&d>=a)
        cout<<b-a<<endl;
    else if(c<=a&&c<=b&&a<=d&&b>=d)
        cout<<d-a<<endl;
    else if(a<=c&&a<=d&&b>=a&&b>=d)
        cout<<d-c<<endl;
    return 0;
}

Measured memory_bytes: 256
n = gets.to_i
sqrt = Math.sqrt(n).to_i + 1
i = 1
min = sqrt
while i < sqrt
  if n % i == 0
    if (n / i).to_s.length <= min
      min = (n / i).to_s.length
    end
  end
  i += 1
end
puts min

Measured memory_bytes: 14348
#include <bits/stdc++.h>
#define S second
#define F first
#define IO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using LL = long long;
using LD = long double;
const int mod = 1e9 + 7;
const LL N = 1e5 + 5;

using namespace std ;

LL arr[N];
int main (){
    LL n;
    cin >> n;
    LL h[n];
    for (int i = 0; i < n; ++i)
        cin >> h[i];
    arr[0] = 0;
    arr[1] = abs(h[0] - h[1]);
    for (int i = 2; i < n; ++i){
        arr[i] = min(abs(h[i - 2] - h[i]) + arr[i - 2], abs(h[i - 1] - h[i]) + arr[i - 1]);
    }
    cout << arr[n - 1] << endl;
}


Measured memory_bytes: 1792
N = int(input())
A = list(map(int,input().split()))

tmp = []
nine = 0
for a in A:
  check = (a - a%400)//400
  if(check < 8):
    tmp.append(check)
  else:
    nine += 1
color = len(list(set(tmp)))
if(color == 0):
  print(1, nine)
else:
  print(color, color+nine)

Measured memory_bytes: 3064
using System;

namespace AtCorder
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine();
            var count = 0;

            if (input[0] == 'o')
            {
                count++;
            }

            if (input[1] == 'o')
            {
                count++;
            }

            if (input[2] == 'o')
            {
                count++;
            }

            var result = count == 0 ? 700 : 700 + 100 * count;

            Console.WriteLine(result);
        }
    }
}

Measured memory_bytes: 25748
#include <bits/stdc++.h>
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")    
using namespace std;
#define lli long long int
#define uli unsigned long long int
#define INF 999999999999
#define rep(i,m,n) for(lli i = m;i < n;i++)
#define rrep(i,m,n) for(lli i=m-1;i>=n;i--)
#define pb(n) push_back(n)
#define UE(N) N.erase(unique(N.begin(),N.end()),N.end());
#define Sort(n) sort(n.begin(), n.end())
#define Rev(n) reverse(n.begin(),n.end())
#define Out(S) cout << S << endl
#define NeOut(S) cout << S
#define HpOut(S) cout << setprecision(50) << S << endl
#define Vec(K,L,N,S) vector<L> K(N,S)
#define DV(K,L,N,M,S) vector<vector<L>> K(N,vector<L>(M,S))
#define TV(K,L,N,M,R,S) vector<vector<vector<L>>> K(N,vector<vector<L>>(M,vector<L>(R,S)))
#define pint pair<lli,lli>
#define paf(L,R) pair<L,R>
#define mod 998244353
#define MAX 10000000
#define ALL(a)  a.begin(),a.end()
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  lli C,D,E,H,W,M,K,L,R,N,num=0,sum=0,flag=0;string S,T;
  long double A,B;
  cin >> A >> B;
  HpOut(floor(A*B));
}

Measured memory_bytes: 3844
n=int(input())
a=list(map(int,input().split()))
x=0
for i in range(n):
    b=0
    if i!=n-1:
        
        if a[i]>a[i+1]:
            b=a[i]-a[i+1]
            a[i+1]=a[i+1]+b
            x+=b
print(x)


Measured memory_bytes: 32276
# coding: utf-8
import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 同じ地点で銀貨の枚数によって別の状態として扱う（最大max(A)*(N-1))
N, M, S = lr()
UVAB = [lr() for _ in range(M)]
CD = [lr() for _ in range(N)]  # 0-indexed
Amax = 0
for i in range(M):
    a = UVAB[i][2]
    if a > Amax:
        Amax = a

limit = Amax*(N-1)
S = min(S, limit)
graph = [[] for _ in range(N+1)] # 1-indexed
for u, v, a, b in UVAB:
    graph[u].append((v, a, b))
    graph[v].append((u, a, b))

def dijkstra(start):
    # 時間、銀貨の枚数、現在地をqueへ
    INF = 10 ** 15
    dist = [[INF for _ in range(limit+1)] for _ in range(N+1)]
    dist[1][S] = 0
    que = [(0, S, 1)]
    while que:
        time, silver, prev = heappop(que)
        if dist[prev][silver] < time:
            continue
        for next, a, b in graph[prev]:
            t = time + b
            si = silver - a
            if si < 0:
                continue
            if dist[next][si] > t:
                dist[next][si] = t
                heappush(que, (t, si, next))
        c, d = CD[prev-1]
        si = min(limit, silver+c)
        while dist[prev][si] > time + d:
            dist[prev][si] = time + d
            heappush(que, (time+d, si, prev))
            si += c; si = min(limit, si)
            time += d
            
    return dist

dist = dijkstra(1)
for i in range(2, N+1):
    d = dist[i]
    answer = min(d)
    print(answer)

# 前解いたものをPyPyで

Measured memory_bytes: 120964
K,X = [int(i) for i in input().split(" ")]
li = []
li1 = []
for i in range(K):
    ans = X - i
    li.append(ans)
    ans1 = X + i
    li1.append(ans1)
    
k = li[::-1] + li1[1:]
for ele in k:
    print(ele , end = " ")


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define rrep(i,n) for(int i=1; i<=(int)(n); i++)
#define pb push_back
#define all(v) v.begin(),v.end()
#define fi first
#define se second
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<string> vs;
typedef vector<char> vc;
typedef long long ll;
typedef unsigned long long ull;

//const ll mod = 1000000007;

int main() {
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    int takahashi = c / b;
    int aoki = a / d;
    if(c % b != 0) takahashi++;
    if(a % d != 0) aoki++;
    string ans = takahashi <= aoki ? "Yes" : "No";
    cout << ans << endl;
}

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

int main(){
  int A,B,C,D,E,F,G,H,I,J;
  cin >> A >> B >> C >> D;
  E=max(A,B)-min(A,B);
  F=max(A,C)-min(A,C);
  G=max(C,B)-min(C,B);
  if(F<=D){
    cout << "Yes" << endl;
  }
  else if(E<=D&&G<=D){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 3608
N, M = map(int, input().split())
H = list(map(int, input().split())) 
A = [0]*M
B = [0]*M
for i in range(M):
    A[i], B[i] = map(int, input().split())
    A[i] -= 1
    B[i] -= 1
lis = []
for i in range(M):
    if H[A[i]] < H[B[i]]:
        lis.append(A[i])
    if H[A[i]] == H[B[i]]:
        lis.append(A[i])
        lis.append(B[i])
    if H[A[i]] > H[B[i]]:
        lis.append(B[i])
print(len(H)-len(set(lis)))

Measured memory_bytes: 24528
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(ll i = 0; i < (n); ++i)
#define rep1(i, n) for(ll i = 1; i < (n); ++i)
#define rep4(i, start, end, step) for (ll i = (start); i < (end); i += (step))

#define BIG_PRIME 1000000007
#define BP_remainder(x) ((x) % BIG_PRIME)

#define INF 0x3fffFFFF
#define INF_NEG (INF * -1)
#define INF_LONG (INF << 32)
#define INF_LONG_NEG (INF_LONG * -1L)

typedef long long ll;
typedef char str255[256];
// char *用、strlen の ll 版
ll StrLen(char *s) { for(ll ptr = 0L;; ++ptr) if(!s[ptr]) return ptr; } 
// char * の後ろから n 文字削除, 削除後の文字数を返す
ll StrDel(char *s, int n) { ll l = StrLen(s); s[l - n + 1L] = '\0'; return l - n; }
// 正の整数の桁数
ll NumDigits(ll l){ char s[30]; sprintf(s, "%lld", l); return StrLen(s); }

int isFirst = 1;
template <class T> 
void print(T t) { if (isFirst) cout << t, isFirst = 0; else cout << " " << t; }

void chmin(ll& a, ll b) { if (a > b) a = b; }
void chmax(ll& a, ll b) { if (a < b) a = b; }

signed main()
{
    cout << fixed << setprecision(9);

    string S; cin >> S;
    vector<ll> abc(128, 0);
    rep(i, 4) ++abc[S[i]];
    ll count = 0L;
    rep4(i, 'A', 'Z' + 1, 1) if (abc[i] == 2) ++count;
    if (count == 2) puts("Yes");
    else puts("No");
    return 0;
}


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

using namespace std;

const int maxn=2e5+5;
typedef long long ll;

vector<int> a[30];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	string s,t;
	cin>>s>>t;
	int l=s.length();
	int l2=t.length();
	ll ans=0;
	for(int i=0;i<l;++i){
		a[s[i]-'a'].push_back(i);
	}
	int cnt=-1;
	for(int i=0;i<l2;++i){
		if(a[t[i]-'a'].size()==0){
			cout<<-1<<endl;return 0;
		}
		int k=upper_bound(a[t[i]-'a'].begin(),a[t[i]-'a'].end(),cnt)-a[t[i]-'a'].begin();
		if(k==a[t[i]-'a'].size()){
			ans+=l;cnt=a[t[i]-'a'][0];
		}
		else cnt=a[t[i]-'a'][k];
	}
	printf("%lld",ans+1+cnt);
	return 0;
}

Measured memory_bytes: 1228
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		while(true){
			int n = sc.nextInt();
			if(n==0) break;
			
			String s = sc.next();
			int ba = 0;
			int[] te = new int[n];
			for(int i=0;i<100;i++){
				if(s.charAt(i)=='M'){
					te[i%n]++;
				}else if(s.charAt(i)=='S'){
					ba += te[i%n] + 1;
					te[i%n] = 0;
				}else{
					te[i%n] += ba + 1;
					ba = 0;
				}
			}
			Arrays.sort(te);
			for(int i=0;i<n;i++) System.out.print(te[i] + " ");
			System.out.println(ba);
		}
	}
}

Measured memory_bytes: 21716
n = int(input())
a = list(map(int,input().split()))
dp = [[0]*(n+1) for j in range(n+1)]

## dp[j][i]:iは始点、jは列の長さを表す
for i in range(n):
  dp[0][i] = 0

for j in range(1,n+1):
  for i in range(n):
    if i+j <= n:
      dp[j][i] = max(a[i]-dp[j-1][i+1],a[i+j-1]-dp[j-1][i])
print(dp[n][0])

Measured memory_bytes: 112860
#include<bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(n); ++i)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,b,c,d;
  cin >> a >> b >> c >> d;
  int i,j;
  i = c - a;
  j = d - b;
  c -= j;
  d += i;
  cout << c <<" "<< d <<" ";
  c -= i;
  d -= j;
  cout << c << " " << d << endl;
  return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<cstring>
#include<deque>

char s[100001];
std::deque <char> dq;
std::deque <char>::iterator i;

int main() {
    std::cin >> s;
    for(int i = 0;s[i];i++) dq.push_back(s[i]);
    int q,t,f,r = 0; char c; 
    std::cin >> q;
    while(q--) {
        std::scanf("%d",&t);
        if(t == 1) {
            r ^= 1;
        } else {
            std::scanf("%d %c",&f,&c);
            if(r) f = ((f - 1) ^ 1) + 1;
            if(f == 1) dq.push_front(c);
            if(f == 2) dq.push_back(c);
        }
    }
    if(r) {
        for(i = dq.end() - 1;i != dq.begin();i--) std::putchar(*i);
        std::putchar(*i);
        std::putchar('\n');
    } else {
        for(i = dq.begin();i != dq.end();i++) std::putchar(*i);
        std::putchar('\n');
    }
    return 0;
}

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

int main() {
	int H, N;
	cin >> H >> N;
	int A;
	for (int i = 0; i < N; i++) {
		cin >> A;
		H -= A;
	}
	cout << ((H <= 0) ? "Yes" : "No") << endl;
	return 0;
}

Measured memory_bytes: 256
//
//  atcoder.cpp
//
//
///
#include <bits/stdc++.h>
#include <boost/optional.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/bimap/bimap.hpp>
#include <boost/bimap/multiset_of.hpp>
#include <boost/multi_array.hpp>
#include <boost/math/common_factor.hpp>
#include <boost/icl/interval_map.hpp>
#include <boost/algorithm/string.hpp>
#include <boost/pending/disjoint_sets.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/kruskal_min_spanning_tree.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/numeric/ublas/vector.hpp>
#include <boost/multiprecision/cpp_int.hpp>
// ↓これいる？
#include <boost/graph/strong_components.hpp>

#define REP(i, N) for(int i=0; i<(N); i++)
#define REC(f, ...) (void)0; const auto f = [&](const auto f, __VA_ARGS__)
using namespace std;
using namespace boost::math;
using namespace boost::numeric;
using namespace boost::multiprecision;
using ll = long long;
namespace bst = boost;
template<class T> void fill(T& v) { for (auto&& i : v) cin >> i; }

//#include "atcoder.hpp"

int main() {
    int N;string S;
    
    cin >> N >> S;
  
    if (N % 2 == 1) {
      cout << "No" << endl;
      return 0;
    }
  
    int i = 0, half = N / 2;
  
    while (half < N)
      if (S[i++] != S[half++]) {
        cout << "No" << endl;
        return 0;
      }
    
    cout << "Yes" << endl;
    
    return 0;
}







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

//for
#define REP(i,n) for(int i=0,i##_len=(int)(n);i<i##_len;i++)
#define REPS(i,n) for(int i=1,i##_len=(int)(n);i<=i##_len;i++)
#define RREP(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define RREPS(i,n) for(int i=(int)(n);i>0;i--)

//printf
#define PRINTD(d) printf("%d\n",(d))
#define PRINTS(s) printf("%s\n",(s))

//memset
#define m0(s) memset(s,0,sizeof(s))
#define ml(s) memset(s,63,sizeof(s))
#define fill(s,c) memset(s,c,sizeof(s))

typedef long long ll;

int Min(int a, int b) {
	return (a)<(b) ? (a) : (b);
}
ll Max(int a, int b) {
	return (a) > (b) ? (a) : (b);
}

int main() {
	int n,a;
	scanf("%d %d", &n,&a);
	if (n % 500 <= a) {
		puts("Yes");
	}
	else {
		puts("No");
	}
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <numeric>
#include <algorithm>
#include <iomanip>
#define _USE_MATH_DEFINES
#include <cmath>
#include <math.h>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <thread>///////////////////

#define rep(i,m,n) for(int i=(m);i<(n);i++)
#define rem(i,m,n) for(int i=(m);i>(n);--i)

#define MOD 1000000007
//#define MOD 998244353

using namespace std;

using ll = long long int;
using std::swap;

vector<int> v;
vector<int> w;
vector<long long int> vll;
vector<long long int> wll;
//vector<vector<int>> vec(50, vector<int>(4, 0));
vector<vector<int>> vv;
vector<vector<int>> ww;


int main() {
	string S,T;
	int K;
	cin >> K >> S;
	if (S.length() <= K) {
		cout << S << '\n';
	}
	else {
		T = S.substr(0, K);
		cout << T << "..." << '\n';
	}
	return 0;
}

Measured memory_bytes: 3624
#include<iostream>

using namespace std;

int main(){
    int N;
    cin >> N;
    long A[N];
    long B[N];
    long sum = 0;
    for(int i=0; i<N; i++){
        cin >> A[i];
        sum += A[i];
    }
    
    int bp;
    
    B[0] = A[0];
    for(int i =1; i < N; i++){
        B[i] = B[i-1] + A[i];
        if(sum - 2 * B[i] <= 0){
            bp = i;
            break;
        }
    }

    long ans = min(abs(sum - 2 * B[bp]), sum - 2 * B[bp-1]);

    cout << ans << endl;
    return 0;

}

Measured memory_bytes: 3328
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

lst = primes(100003)
X=int(input())
for i in lst:
    if i>=X:
        print(i)
        exit()


Measured memory_bytes: 4072
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <string>
#include <set>
#include <bitset>
#include <unordered_map>

using namespace std;
using ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;
template <class T>
using Vvec = vector<vector<T> >;

template <class T>
void debug(T& v)
{
    for(auto& x: v) cout << x << " ";
    cout << endl;
}

int main()
{
    int N, K;
    cin >> N >> K;
    vector<ll> p(N);
    for(auto& x: p) cin >> x;

    ll S = 0;
    for(int i=0; i<K; i++) S += 1 + p[i];

    ll ans = S;
    for(int i=K; i<N; i++){
        S += p[i];
        S -= p[i-K];
        ans = max(ans, S);
    }

    printf("%.15f\n", 1.0 * ans / 2.0);
}

Measured memory_bytes: 1792
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<pair<ll, ll>>> vvpll;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;

vvpll G;
vl visited;
vl d;
bool ok = true;

void dfs(ll v, ll dist) {
    if(visited[v]) {
        if(d[v] != dist) {
            ok = false;
        }
        return;
    }
    visited[v] = 1;
    d[v] = dist;
    for(auto p : G[v]) {
        ll u = p.first;
        ll cost = p.second;
        dfs(u, d[v] + cost);
    }
}

int main() {
    ll n, m;
    cin >> n >> m;    

    G.resize(n);
    rep(i, m) {
        ll L, R, D;
        cin >> L >> R >> D;
        L--;  R--;
        G[L].pb(make_pair(R, D));
        G[R].pb(make_pair(L, -D));
    }

    visited.resize(n);
    d.resize(n);
    rep(v, n) {
        if(!visited[v]) {
            dfs(v, 0);
        }
    }

    if(ok) {
        out("Yes");
    }
    else {
        out("No");
    }
    
    re0;
}

Measured memory_bytes: 16384
from collections import deque

def main():
  n,k=map(int,input().split())
  s=input()
  # maked group
  t=[]
  t.append(s[0])
  x=s[0]
  for i in range(1,n):
    if x!=s[i]:
      t.append(s[i])
      x=s[i]
  #print(t)
  
  j=0
  t=deque(t)
  while j<k:
    if len(t)<=2:
      print(n-1)
      exit(0)
    t.popleft()
    t.popleft()
    j+=1
    
  print(n-1-(len(t)-1))

  
if __name__=='__main__':
  main()

Measured memory_bytes: 10764
#include<bits/stdc++.h>
#include <math.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
int main() {
ll N;
  cin >>N;
  
  vl A(N);
  rep(i,N) {
cin >>A.at(i);
  }
  
  rep(i,N) {
A.at(i)=A.at(i)-(i+1);
  }
  
  ll x=0;
  ll y1=0;
  ll y2=0;
  sort(all(A));
  
  if(N%2!=0) {
x=A.at(N/2);
  }

  
  else {
    long double z=(long double)(A.at(N/2-1)+A.at(N/2))/(long double)2;
    ll y1=floor(z);
    ll y2=ceil(z);
    
    ll sum1=0;
    ll sum2=0;
    rep(i,N) {
sum1 +=abs(A.at(i)-y1);
    }
    rep(i,N) {
sum2+=abs(A.at(i)-y2);
    }
    
    if(sum1<=sum2) {
      
      x=y1;
    }
else {
x=y2;
}
  } 
    ll fin=0;
    rep(i,N) {
fin +=abs(A.at(i)-x);
    }
    
    
    cout<<fin <<endl;
  }


    
    
    
    
  

Measured memory_bytes: 1792
def makelist(n, m):
    return [[0 for i in range(m)] for j in range(n)]

N = int(input())
s = [0]*(N+1)
for i in range(1, N+1):
    s[i] = input()

ss = {}
for i in range(1, N+1):
    now = "".join(sorted(list(s[i])))
    if now in ss:
        ss[now] += 1
    else:
        ss[now] = 1

ans = 0
for v in ss.values():
    if v >= 2:
        ans += v * (v-1) // 2

print(ans)


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

map<string,bool>mp;
bool flag=true;

int main() {
	int n;
	string str,str1="";
	cin>>n;
	for(int i=1; i<=n; i++) {
		cin>>str;
		if(mp.count(str)==0)
			mp[str]=1;
		else
			flag=false;
		if(str1==""){
			str1=str;
			continue;
		}
		if(str1[str1.length()-1]!=str[0])
			flag=false;
		str1=str;
	}
	if(flag)
		puts("Yes");
	else
		puts("No");
	return 0;
}


Measured memory_bytes: 256
import traceback
import fractions
from functools import reduce

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

class PrimeFractorization:
    def __init__(self):
        self.a = 2

    def decomposit_prime(self, n):
        res = []
        try:
            while n >= self.a * self.a:
                if n % self.a == 0:
                    res.append(self.a)
                    #print(self.a, "* ", end="")
                    n //= self.a
                else:
                    self.a += 1

            res.append(n)
            
            return res

        except Exception as e:
            raise

N,P = map(int,input().split())

obj = PrimeFractorization()
factor = obj.decomposit_prime(P)

res_fac = factor[:N]
amari = factor[N:]

index = 0
for i in amari:
    if len(res_fac)-1 < index:
        index = 0
    res_fac[index] *= i
    index += 1

print(gcd_list(res_fac))

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

#define mod 1000000007
 ll dp[1005][1005];
string s[1005];

void solve(ll h,ll w){
   if(h<1||w<1) {dp[h][w]=0;return;}
   if(h==1&&w==1) {dp[h][w]=1;return;}
   if(dp[h][w]>=0) return ;
   if(s[h-1][w-1]=='#') {dp[h][w]=0; return;}
	solve(h-1,w);
	solve(h,w-1);
   dp[h][w]=(dp[h-1][w]+dp[h][w-1])%mod;

}








int main(){
	ll h,w;
	cin>>h>>w;
	
	for(int i=0;i<h;i++) cin>>s[i];
     
   
    for(int i=0;i<=h;i++) for(int j=0;j<=w;j++) dp[i][j]=-1;
    solve(h,w);
    cout<<dp[h][w]<<endl;



}

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  long long n, ans = 0, a;
  cin >> n;
  for (int i=0; i < n; i++) {
    long long x = 0;
    cin >> a;
    while (a%2 == 0) {
      x++;
      a /= 2;
    }
    ans += x;
  }
  cout << ans << '\n';
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <stack>
#include <utility>
#include <numeric>
#include <algorithm>
#include <functional>
#include <cctype>
#include <complex>
#include <string>
#include <sstream>
#include <fstream>
#include <cassert>
using namespace std;

//common
typedef int  i32;
typedef long long i64,ll;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef long long ll; typedef vector<long long> vl; typedef pair<long long,long long> pll; typedef vector<pair<long long,long long> > vpll;
typedef vector<string> vs; typedef long double ld;

#define BR "\n"
#define ALL(c) (c).begin(),(c).end()
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define EACH(it,o) for(auto it = (o).begin(); it != (o).end(); ++it)
#define IN(l,v,r) ((l)<=(v) && (v)<(r))

//config
//#undef NDEBUG
//#define INF 1<<30
//#define EPS 1e-8
//const ll MOD =100000007;

//debug
#ifdef NDEBUG
#define DUMP(x)
#define DUMPLN(x)
#define DEBUG(x)
#define DEBUGLN(x)
#define LINE()
#define LINELN()
#define CHECK(exp,act)
#define STOP(e)
#else
#define DUMP(x)  cerr << #x << " = " << (x)
#define DUMPLN(x)  DUMP(x) <<endl
#define DEBUG(x) DUMP(x) << LINE() << " " << __FILE__
#define DEBUGLN(x) DEBUG(x)<<endl
#define LINE()    cerr<< " (L" << __LINE__ << ")"
#define LINELN()    LINE()<<endl
#define CHECK(exp,act)  if(exp!=act){DUMPLN(exp);DEBUGLN(act);}
#define STOP(e)  CHECK(e,true);if(!(e)) exit(1);
#endif

template<class T> inline string toString(const vector<T>& x) {
	stringstream ss;
	REP(i,x.size()){
		if(i!=0)ss<<" ";
		ss<< x[i];
	}
	return ss.str();
}

template<class T> inline string toString(const vector<vector<T> >& map) {
	stringstream ss;
	REP(i,map.size()){
		if(i!=0)ss<<BR;
		ss<< toString(map[i]);
	}
	return ss.str();
}
template<class K,class V>  string toString(map<K,V>& x) {
	string res;stringstream ss;
	for(auto& p:x)ss<< p.first<<":" << p.second<<" ";
	return ss.str();
}

string BITtoString(int bit){
    stringstream ss;
    while(bit!=0){ss<<(bit%2);bit/=2;}
    string res=ss.str();reverse(ALL(res));
    return res;
}

template<typename T,typename V> inline T mod(T v,V MOD){
	return (v%MOD+MOD)%MOD;
}
int hmap[2005000],wmap[2005000];
		    
class Main{
public:

	void run(){
		while(true){
			int N,M;cin >> N >> M ;if(N==0 && M==0)break;
			vector<int> hs(N),ws(M);
			REP(i,N)cin >> hs[i];
			REP(i,M)cin >> ws[i];

			vector<int> hsum(N+1),wsum(M+1);
			for(int i=1;i<=N;i++)hsum[i]=hsum[i-1]+hs[i-1];
			for(int i=1;i<=M;i++)wsum[i]=wsum[i-1]+ws[i-1];


			fill_n(hmap,2005000,0);
			fill_n(wmap,2005000,0);

		    for(int i=0;i<=N;i++)for(int j=i+1;j<=N;j++){
		    	hmap[hsum[j]-hsum[i]]++;
		    }
		    for(int i=0;i<=M;i++)for(int j=i+1;j<=M;j++){
		    	wmap[wsum[j]-wsum[i]]++;
		    }
		  
		    ll res=0;
		    for(int i=1;i<2005000;i++){
		    	res+=(ll)hmap[i]*wmap[i];
		    }
		    cout << res <<endl;
		}
	}
};

 int main(){
ios::sync_with_stdio(false);
 	Main().run();
 	return 0;
 }

Measured memory_bytes: 16892
import itertools
N = int(input())
AGCs = [
    'AGC',
    'GAC',
    'ACG',
    'AGAC',
    'AGGC',
    'AGTC',
    'ACGC',
    'ATGC',
]
seq = ["A", "G", "C", "T"]
from collections import Counter
memo = Counter()

count = 0
new_S = []
def memo_saiki(n, start_memo):
    if n==1:
        print(4)
        exit()
    if n==2:
        print(16)
        exit()
    memo = start_memo
    new_memo = Counter()
    for _ in range(n-3):
        for k, v in memo.items():
            for char in 'AGCT':
                target = k+char
                if any([agc in target for agc in AGCs]):
                    continue
                new_memo.update({target[-3:]: v})
        memo = new_memo
        new_memo = Counter()
    print(sum([v for v in memo.values()]) % (10**9 + 7))

def saiki(n=6):
    S = ['']
    new_S = []
    memo = {}
    for _ in range(n):
        for i, s in enumerate(S):
            for c in 'AGCT':
                memo[s[-3:]] = 1
                hoge = s[-3:] + c
                if any([agc in hoge for agc in AGCs]):
                    continue
                new_S.append(hoge)
        S = new_S
        new_S = []
    #S = new_S.copy()
    return S
memo_saiki(n=N, start_memo = Counter(saiki(3)))



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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second

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

void Main()
{
	int n, a;
  	cin >> n >> a;
	cout << n*n-a << endl;
	return;
}

int main()
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
	return 0;
}


Measured memory_bytes: 256
n = int(input())
t = list(map(int, input().split()))

m = int(input())
p, x = [0] * m, [0] * m
for i in range(m):
    p[i], x[i] = map(int, input().split())
ans = sum(t)
for i in range(m):
    print(ans - t[p[i] - 1] + x[i])
    

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define z 500000000000000000
#define sh 500000

int main()
{

	
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n,i,j;
	cin>>n;
	int ar[n+1][4];
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=3;j++)
			cin>>ar[i][j];
	}
	int dp[n+1][4];
	for(i=1;i<=3;i++)
		dp[1][i]=ar[1][i];
	for(i=2;i<=n;i++)
	{
		dp[i][1]=max(dp[i-1][2]+ar[i][1],dp[i-1][3]+ar[i][1]);
		dp[i][2]=max(dp[i-1][1]+ar[i][2],dp[i-1][3]+ar[i][2]);
		dp[i][3]=max(dp[i-1][1]+ar[i][3],dp[i-1][2]+ar[i][3]);
	}
	cout<<max(max(dp[n][1],dp[n][2]),dp[n][3]);

}

Measured memory_bytes: 3328
#include<stdio.h>
#include<stdlib.h>
int asc(const void* a, const void* b)
{
	if (*(long long int*)a > * (long long int*)b)return 1;
	if (*(long long int*)a < *(long long int*)b)return -1;
	return 0;
}
int main()
{
	long long int w, h;
	scanf("%lld %lld", &w, &h);
	long long int i, j;
	long long int p[100005], q[100005];
	for (i = 0; i < w; i++)
		scanf("%lld", &p[i]);
	for (j = 0; j < h; j++)
		scanf("%lld", &q[j]);
	qsort(p, w, sizeof(long long int), asc);
	qsort(q, h, sizeof(long long int), asc);
	long long int ans = 0;
	i = j = 0;
	for (;;)
	{
		if (i == w)
		{
			ans += q[j];
			j++;
		}
		else if (j == h)
		{
			ans += p[i];
			i++;
		}
		else
		{
			if (q[j] < p[i])
			{
				ans += q[j] * (w - i + 1);
				j++;
			}
			else
			{
				ans += p[i] * (h - j + 1);
				i++;
			}
		}
		if (i == w && j == h)
			break;
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 2556