akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n,k;
  cin>>n>>k;
  vector<int> vec(n);
  int i=0,j=0,tmp,del;
  for(i=0;i<k;i++){
    cin>>tmp;
    for(j=0;j<tmp;j++){
      cin>>del;
      vec.at(del-1)=1;
    }
  }
  int count=0;
  for(i=0;i<n;i++){
  	if(vec.at(i)==0){count++;}
  }
  cout <<count<< endl;
  return 0;
}

Measured memory_bytes: 3604
using System;
using System.Linq;
using static System.Console;

namespace ConsoleAppAtCoderABC172
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = int.Parse(ReadLine());
            var a = ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();

            var ans = 0;

            for (int i = 1; i <= N; i++)
            {
                if (i % 2 == 1 && a[i - 1] % 2 == 1)
                    ans++;
            }

            WriteLine(ans);
        }
    }
}


Measured memory_bytes: 28220
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define irep(i, n) for (int i = (n); i >= 0; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1 << 25;
const int MOD = 1e9+7;
 
int main() {
	string s, t;
	cin >> s >> t;
	int ls =s.size(), lt = t.size();
	int ans = lt;
	for (int i = 0; i <= ls-lt; i++)
	{
		int cnt = 0;
		for (int j = 0; j < lt; j++)
		{
			if (s[i+j] != t[j]) cnt++;
		}
		ans = min(ans, cnt);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3628
use std::io::{self, Read, Write};

#[rustfmt::skip] #[macro_use] #[allow(unused_macros)]
mod rwc {
    macro_rules! rd { ($buf:ident, $t:ty)       => { $buf.next().unwrap().parse::<$t>().ok().unwrap() }; }
    macro_rules! wt { ($out:ident, $($arg:tt)*) => { write!($out, $($arg)*).ok()                      }; }
    macro_rules! cv { ($n:expr, $fn:expr)       => { (0..$n).map($fn).collect::<Vec<_>>()             }; }
}

fn main() {
    let (mut _buf, mut _out) = (String::new(), io::stdout());
    let (mut _buf, mut _out) = {
        io::stdin().read_to_string(&mut _buf).ok();
        (_buf.split_whitespace(), io::BufWriter::new(_out.lock()))
    };

    let mut n = rd!(_buf, u32);

    let mut ok = false;
    while n > 0 {
        if n % 10 == 7 {
            ok = true;
        }
        n /= 10;
    }
    if ok {
        wt!(_out, "Yes\n");
    } else {
        wt!(_out, "No\n");
    }
}


Measured memory_bytes: 2144
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
const int INF = 1000000009;
struct ban
{
    int l, r;
    ban(){}
    ban(int l, int r)
    {
        this->l = l;
        this->r = r;
    }
};
bool operator<(const ban& a, const ban& b)
{
    return a.r < b.r;
}

int n;
ban a[N];

int p[N];
int dp[N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
    {
        int x, l;
        scanf("%d%d", &x, &l);
        a[i] = ban(x - l, x + l);
    }
    sort(a + 1, a + n + 1);
    int ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        int l = 1, r = i - 1;
        int u = 0;
        while (l <= r)
        {
            int m = (l + r) / 2;
            if (a[m].r <= a[i].l)
            {
                u = m;
                l = m + 1;
            }
            else
                r = m - 1;
        }
        dp[i] = p[u] + 1;
        p[i] = max(p[i - 1], dp[i]);
    }
    printf("%d\n", p[n]);
    return 0;
}


Measured memory_bytes: 1792
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string>
#include <iostream>
#include <math.h>
#define rep(i,n) for(int i = 0; i <(n); i++)
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;

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

int main(void) {
	int N, i, j, k, tmp, cnt = 0, ans = 0;
	ll A, B, K;
	scanf("%lld %lld",&A,&B);
	K = (A + B) / 2;
	if (K * 2 == A + B) {
		printf("%lld\n", K);
	}
	else {
		printf("IMPOSSIBLE\n");
	}


	
	return 0;
}

Measured memory_bytes: 256
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    A, B = map(int, readline().split())

    def f(x):
        r = (x + 1) % 4
        ans = 0
        for n in range(x, x - r, -1):
            ans ^= n
        return ans

    if A == 0:
        print(f(B))
    else:
        print(f(B) ^ f(A - 1))

    return


if __name__ == '__main__':
    main()


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

typedef struct{
    int a,b;
    int ai,bi;
}aaa;
typedef struct{
    int h,i;
}bbb;

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

    vector<int> flg(n,0);
    vector<bbb> h(n);
    vector<aaa> a(m);

    for(int i=0;i<n;i++){
        cin>>h[i].h;
        h[i].i=i;
    }

    for(int i=0;i<m;i++){
        cin>>a[i].a>>a[i].b;
        flg[a[i].a-1]=1;
        flg[a[i].b-1]=1;
        a[i].ai=a[i].a-1;
        a[i].bi=a[i].b-1;
        a[i].a=h[a[i].a-1].h;
        a[i].b=h[a[i].b-1].h;
    }
    //sort(h.begin(),h.end());
    //sort(a.begin(),a.end());
    int cnt=0;
    for(int i=0;i<n;i++){
        if(flg[i]==0){
            cnt++;
            //cout<<"---"<<i<<endl;
        }
    }
    for(int i=0;i<m;i++){
        if(a[i].a>=a[i].b){
            flg[a[i].bi]=0;
        }
        if(a[i].b>=a[i].a){
            flg[a[i].ai]=0;
        }
    }
    for(int i=0;i<n;i++){
        if(flg[i]==1){
            cnt++;
            //cout<<i<<endl;
        }
    }

    /*
    for(int i=0;i<m;i++){
        cout<<a[i].a<<" "<<a[i].b<<endl;
    }*/

    cout<<cnt<<endl;
    return 0;
}

Measured memory_bytes: 5900
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    ll x;
    cin>>x;
    double v = (double)sqrt((double)sqrt(x));
    int val = v+1;
    for(int i = -val;i <= val; ++i){
        for(int j = -val;j <= val; ++j){
            ll vv = i;vv*=i;vv*=i;vv*=i;vv*=i;
            ll uu = j;uu*=j;uu*=j;uu*=j;uu*=j;
            if(vv-uu==x){
                cout<<i<<' '<<j<<'\n';
                return 0;
            }
        }
    }
}
   // cout<<"complete"<<'\n';

Measured memory_bytes: 3668
#include "bits/stdc++.h"

#define MOD 1000000007
#define rep(i, n) for(ll i=0; i < (n); i++)
#define ALL(v) v.begin(),v.end()
#define DUMP(i, v)for(ll i=0;i<v.size();i++)cout<<v[i]<<" "

using namespace std;
typedef long long int ll;
typedef vector<ll> llvec;
typedef vector<double> dvec;
typedef pair<int, int> P;
struct Edge{ll from, to, cost;};

ll mod(ll a, ll mod){
  ll res = a%mod;
  if(res<0)res=res + mod;
  return res;
}

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

ll modinv(ll a, ll mod){
  return modpow(a, mod-2, mod);
}

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

bool is_prime(ll n){
  ll i = 2;
  if(n==1)return false;
  if(n==2)return true;
  bool res = true;
  while(i*i <n){
    if(n%i==0){
      res = false;
    }
    i = i+1;
  }

  //if(i==1)res = false;
  if(n%i==0)res=false;
  return res;
}


/**************************************
** A main function starts from here  **
***************************************/
int main(){
  ll N; cin >> N;
  llvec vc;
  llvec v(N), c(N);
  rep(i, N){
    cin >> v[i];
  }
  rep(i, N){
    cin >> c[i];
    vc.push_back(v[i]-c[i]);
  }
  sort(ALL(vc), [] (ll a, ll b){return a>b;});
  ll ans = 0;
  ll i=0;
  while(vc[i]>0){
    ans += vc[i];
    i++;
  }

  cout << ans;
  return 0;
}


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

void swap( int* a, int* b )
{
  int tmp;
  tmp = *a;
  *a = *b;
  *b = tmp;
}

int BubbleSort( int* lst, int length )
{
  int count = 0;
  for (int i=1; i<length; i++)
  {
    for (int j=0; j<length-i; j++)
    {
      if ( lst[j] > lst[j+1] )
      {
        swap( &lst[j], &lst[j+1] );
        count++;
      }
    }
  }
  return count;
}

int main()
{
  while(true)
  {
    int n;
    cin >> n;
    if ( n == 0 ) break;
    int* arr = new int[n];
    for (int i=0; i<n; i++)
    {
      cin >> arr[i];
    }

    int count = BubbleSort( arr, n );

    cout << count << endl;

    delete[] arr;
  }
}

Measured memory_bytes: 1196
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define MOD 1000000007
#define INF (1<<30)
#define LINF (lint)(1LL<<56)
#define endl "\n"
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define Flag(x) (1<<(x))
#define Flagcount(x) __builtin_popcount(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
#define plint pair<lint,lint>
#define fi first
#define se second
typedef long long lint;
int dx[8]={1,1,0,-1,-1,-1,0,1};
int dy[8]={0,1,1,1,0,-1,-1,-1};

int main(void){
    int N,M;
    cin >> N >> M;
    int ans=0;
    ans+=(N*(N-1))/2;
    ans+=(M*(M-1))/2;
    cout << ans << endl;
}

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

typedef long long ll;
ll mod = 1e9 + 7;

const int N = 1e2 + 10, K = 1e5 + 10;
ll a[N], dp[N][K], ps[K];

int main()
{
	ll n, k;
	cin >> n >> k;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 0; i <= a[1]; i++) dp[1][i] = 1;
	ps[1] = dp[1][0];
	for (int i = 2; i <= k + 1; i++)
	{
		ps[i] = ps[i - 1] + dp[1][i - 1];
		ps[i] %= mod;
	}
	for (int i = 2; i <= n; i++)
	{
		for (ll j = 0; j <= k; j++)
		{
			dp[i][j] = ps[j + 1] - ps[max(j - a[i], 0ll)];
			dp[i][j] %= mod;
		}
		ps[1] = dp[i][0];
		for (int j = 2; j <= k + 1; j++)
		{
			ps[j] = ps[j - 1] + dp[i][j - 1];
		}
	}
	cout << dp[n][k];
}


Measured memory_bytes: 82440
h, w = map(int, input().split())
temp = [input() for _ in range(h)]

s = [[""]*w for _ in range(h)]

# python, list(文字列)とすれば1文字ずつを要素とするlistができる
# 別に文字列のまま扱ってもよさそう
for i in range(h):
    s[i] = list(temp[i])

ns = [[0]*w for _ in range(h)]

# 文字列がタプル同様あとから変更できない仕様に悩まされた
# 文字列として受け取るのではなく，リストで最初から受け取ればよい

# なんでこれリストnsがまとめて書き換わってしまうんだ
# -> https://note.nkmk.me/python-list-initialize/
  # 要素のリストがすべて同じオブジェクトになってしまっているらしい
  # s, nsを内包表記で書く必要がある
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            ns[i][j] = "#"

for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            
            if i != 0:
                if ns[i-1][j] != "#": ns[i-1][j] += 1
                if j != 0:
                    if ns[i-1][j-1] != "#": ns[i-1][j-1] += 1
                if j != w-1:
                    if ns[i-1][j+1] != "#": ns[i-1][j+1] += 1
                
            if j != 0:
                if ns[i][j-1] != "#": ns[i][j-1] += 1
            if j != w-1:
                if ns[i][j+1] != "#": ns[i][j+1] += 1

            if i != h-1:
                if ns[i+1][j] != "#": ns[i+1][j] += 1
                if j != 0:
                    if ns[i+1][j-1] != "#": ns[i+1][j-1] += 1
                if j != w-1:
                    if ns[i+1][j+1] != "#": ns[i+1][j+1] += 1

for i in range(h):
    for j in range(w):
        ns[i][j] = str(ns[i][j])

for i in range(h):
    print("".join(ns[i]))

Measured memory_bytes: 3188
#include <stdio.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>

using namespace std;

#define rep(i,x) for(int i=0;i<x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define pb(x) push_back(x)
#define int long long

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


signed main(void) {
  int N;
  cin >> N;
  vector<pair<int, int> > works(N);

  rep(i, N) {
    int a, b;
    cin >> a >> b;
    works[i] = make_pair(a, b);
  }

  sort(works.begin(), works.end(), compare_by_b);

  string str = "Yes";
  int time;
  rep(i, N) {
  	time += works[i].first;
  	if (time <= works[i].second) {

  	} else {
  		str = "No";
  		break;
  	}
  }

  cout << str << endl;

  return 0;
}


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

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

    int ma = 0;
    int ans = 0;
    for (int i = 0; i < N; i++) {
        int H;
        cin >> H;

        ans += (ma <= H);
        ma = max(ma, H);
    }
    cout << ans << endl;
}


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

int main( void )
{
    int n;
    cin >> n;
    if ( ( n - ( n / 100 ) ) % 10 == 0 )
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    return 0;
}


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

int main() {
  int N,K,ans = 0;
  cin >> N >> K;
  vector<int> vec(N,0);
  for(int i=0; i<K; i++){
    int d;
    cin >> d;
    for(int j=0; j<d; j++){
      int a;
      cin >> a;
      vec[a-1] = 1;
    }
  }
  for(int i=0; i<N; i++){
    if(vec[i] == 0){
      ans++;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 3608
import bisect
N = int(input())

base = pow(N, 1/2)
dic = {}
i = 2
li = []
now = 0
count = 0

for j in range(1, 51):
    now += j
    li.append(now)

while N != 1 and i <= base:
    # print(N)
    if N % i == 0:
        dic[i] = 0
        while N % i == 0:
            N /= i
            dic[i] += 1
    i += 1
if N != 1:
    dic[N] = 1
# print(dic)
if len(dic.keys()) == 0:
    if N == 1:
        print(0)
    else:
        print(1)
else:
    # print(li)
    for d in dic.values():
        # print(d)
        count += bisect.bisect_right(li, d)
    print(count)


Measured memory_bytes: 9484
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int n;
  cin >> n;
  vector<int> in(n + 2);
  for (int i = 1; i <= n; i++) {
    cin >> in[i];
  }
  int sum = 0;
  for (int i = 0; i <= n; i++) {
    sum += abs(in[i + 1] - in[i]);
  }
  for (int i = 1; i <= n; i++) {
    cout << sum - abs(in[i] - in[i + 1]) - abs(in[i] - in[i - 1]) + abs(in[i + 1] - in[i - 1]) << endl;
  }
  return 0;
}


Measured memory_bytes: 1664
import sys
import heapq
sys.setrecursionlimit(10**8)
stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


T = ni()

for _ in range(T):
    N = ni()
    ans = 0
    plus = []
    minus = []
    for _ in range(N):
        k, l, r = na()
        if l > r:
            plus.append([k, l-r])
            ans += r
        elif l < r:
            if N != k:
                minus.append([N-k, r-l])
            ans += l
        else:
            ans += l
    plus = sorted(plus, key=lambda x: x[0] * 10 ** 10 - x[1])
    minus = sorted(minus, key=lambda x: x[0] * 10 ** 10 - x[1])
    queue = []
    for p in plus:
        i, v = p 
        if len(queue) < i:
            heapq.heappush(queue, v)
        else:
            if queue[0] < v:
                heapq.heappushpop(queue, v)
    ans += sum(queue)
    queue = []
    for m in minus:
        i, v = m
        if len(queue) < i:
            heapq.heappush(queue, v)
        else:
            if queue[0] < v:
                heapq.heappushpop(queue, v)
    ans += sum(queue)
    print(ans)


Measured memory_bytes: 113776
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
  int n;
  long double t,a;
  cin >> n >> t >> a;
  int ans=1;
  long double mn=10000;
  rep(i,n){
    long double h=0;
    cin >> h;
    long double m=abs((t-h*0.006)-a);
    if(m<mn){
      mn=m;
      ans=i+1;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <stdio.h>

int n, m, i, d, p, r[11];

int main()
{
    while(1)
    {
        scanf("%d", &n);
        scanf("%d", &m);
        
        if(n == 0 && m == 0) { break; }
        
        for(i = 0; i < 11; i++)
        {
            r[i] = 0;
        }
        
        for(i = 0; i < n; i++)
        {
            scanf("%d", &d);
            scanf("%d", &p);
            
            r[p] += d;
        }
        
        for(i = 10; i >= 0; i--)
        {
            if(m >= r[i])
            {
                m -= r[i];
                
                r[i] = 0;
            }
            else
            {
                r[i] -= m;
                
                break;
            }
        }
        
        int sum = 0;
        
        for(i = 0; i <= 10; i++)
        {
            sum += i * r[i];
        }
        
        printf("%d\n", sum);
    }
    
    return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
using namespace std;
using pint = pair<int, int>;
using ll = long long;
using pll = pair<ll, ll>;
#define FOR(i, begin, end) for (int i = (begin), i##_end_ = (end); i < i##_end_; i++)
#define IFOR(i, begin, end) for (int i = (end)-1, i##_begin_ = (begin); i >= i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define FI first
#define SE second
#define endl "\n"
#define ciosup cin.tie(0);ios::sync_with_stdio(false);
constexpr ll INF = 1e9 + 7;
constexpr ll MOD = 1e9 + 7;

int main()
{
    int n, m;
    cin >> n >> m;
    int k[12], s[12][12], p[12], ans = 0;
    REP(i, m)
    {
        cin >> k[i];
        REP(j, k[i])
        {
            cin >> s[i][j];
        }
    }
    REP(i, m)
        cin >> p[i];
    int sw[12];
    for (int bit = 0; bit < (1 << n);++bit)
    {
        REP(j, n)
        {
            if (bit & (1<<j)){
                sw[j] = 1;
            }else{
                sw[j] = 0;
            }
        }

        REP(j, m)
        {
            int count = 0;
            REP(l, k[j])
            {
                count += sw[s[j][l] - 1];
            }
            if (count % 2 != p[j])
                break;
            if (j == m - 1)
                ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define mp make_pair
#define eps 1e-8
using namespace std;
typedef pair<int, int> pii;
int main(){
  int a, b, d;
  while(cin >> a >> b >> d, a){
    int x = 0, y = 0;
    pii ans = mp(1e9, 1e9);
    for(int i = -(d/b) - 1 - b; i <= 100000; i++){
      x = i;
      if((a*x + d) % b != 0)continue;
      y = (a*x + d) / b;
      if(ans.first + ans.second > abs(x) + abs(y)){
	ans = mp(abs(x), abs(y));
      }else if(ans.first + ans.second == abs(x) + abs(y)){
	if(a*ans.first + b*ans.second > a*abs(x) + b*abs(y))
	ans = mp(abs(x), abs(y));
      }
    }
    cout << ans.first << " " << ans.second << endl;
  }
  return 0;
}

Measured memory_bytes: 1160
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#define rep(i,n) for(int i=0;i<(n);i++)
typedef long long ll;

using namespace std;
int main() {
	int n;
	cin >> n;
	vector<int> d(n);
	rep(i, n) cin >> d[i];
	sort(d.begin(), d.end());
	int ans;
	ans = d[n / 2] - d[n / 2 - 1];
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 640
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <math.h>

int main(void) {
    int A, B, C;
    int K;
    int i;

    scanf("%d %d %d", &A, &B, &C);
    scanf("%d", &K);

    for(i = 0; i < K; i++) {
        if( B <= A ) {
            B *= 2;
        }
        else if( C <= B ) {
            C *= 2;
        }

        if( (B > A) && (C > B) ) {
            break;
        }
    }

    if( (B > A) && (C > B) ) {
        printf("Yes\n");
    }
    else {
        printf("No\n");
    }

    return 0;
}


Measured memory_bytes: 1660
//{{{
#[allow(unused_macros)]
macro_rules! getl {
    ( $( $t:ty ),* ) => {
        {
            let mut s = String::new();
            std::io::stdin().read_line(&mut s).unwrap();
            let s = s.trim_right();
            let mut ws = s.split_whitespace();
            ($(ws.next().unwrap().parse::<$t>().unwrap()),*)
        }
    };
}

#[allow(unused_macros)]
macro_rules! getl_vec {
    ( $t:ty ) => {{
        let mut s = String::new();
        std::io::stdin().read_line(&mut s).unwrap();
        let s = s.trim_right();
        s.split_whitespace()
            .map(|x| x.parse().unwrap())
            .collect::<Vec<$t>>()
    }};
}
//}}}

const INF: u64 = (1 << 31) - 1;

fn main() {
    const ADD: u64 = 0;
    const GETSUM: u64 = 1;

    let (n, q) = getl!(usize, usize);
    let mut queries = vec![];
    for _ in 0..q {
        queries.push(getl!(u64, u64, u64));
    }

    let op = |a, b| a + b;
    let mut segtree = SegmentTree::new(&vec![0; n], &op, 0);
    for (ty, a, b) in queries {
        if ty == ADD {
            let a = a - 1;
            let u = segtree.get(a as usize);
            segtree.update(a as usize, u + b);
        } else {
            let a = a - 1;
            let b = b - 1;
            let ans = segtree.query(a as usize, b as usize + 1);
            println!("{}", ans);
        }
    }
}

struct SegmentTree<T, F> {
    len: usize,
    data: Vec<T>,
    operator: F,
    unit: T,
}

impl<T, F> SegmentTree<T, F>
where
    F: Fn(T, T) -> T + Copy,
    T: Clone + Copy,
{
    // const INF: u64 = std::u64::MAX >> 2;

    fn new(v: &Vec<T>, operator: F, unit: T) -> SegmentTree<T, F> {
        let n = v.len();
        let mut len = 1;
        while len < n {
            len *= 2;
        }

        let mut segtree = SegmentTree {
            len: len,
            data: vec![unit; 2 * len - 1],
            operator,
            unit,
        };

        for i in 0..n {
            segtree.data[i + segtree.len - 1] = v[i];
        }
        for i in (0..(segtree.len - 1)).rev() {
            segtree.data[i] = operator(segtree.data[2 * i + 1], segtree.data[2 * i + 2]);
        }

        segtree
    }

    fn update(&mut self, k: usize, a: T) {
        let data = &mut self.data;
        let mut k = k + self.len - 1;
        data[k] = a;
        while k > 0 {
            k = (k - 1) / 2;
            data[k] = (self.operator)(data[k * 2 + 1], data[k * 2 + 2]);
        }
    }

    fn get(&self, k: usize) -> T {
        self.data[k + self.len - 1]
    }

    fn query(&self, a: usize, b: usize) -> T {
        self.process_query(a, b, 0, 0, self.len)
    }

    fn process_query(&self, a: usize, b: usize, k: usize, l: usize, r: usize) -> T {
        if r <= a || b <= l {
            return self.unit;
        }

        if a <= l && r <= b {
            self.data[k]
        } else {
            let vl = self.process_query(a, b, k * 2 + 1, l, (l + r) / 2);
            let vr = self.process_query(a, b, k * 2 + 2, (l + r) / 2, r);
            (self.operator)(vl, vr)
        }
    }
}



Measured memory_bytes: 12084
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

def func(y, x, cnt):
    if y == h - 1 and x == w - 1:
        cnt += 1
        return y, x, cnt
    if y < h - 1 and a[y + 1][x] == 1:
        cnt += 1
        return func(y + 1, x, cnt)
    if x < w - 1 and a[y][x + 1] == 1:
        cnt += 1
        return func(y, x + 1, cnt)
    if y < h - 1 and a[y + 1][x] == 0:
        return y, x, cnt
    if x < w - 1 and a[y][x + 1] == 0:
        return y, x, cnt

h, w = MAP()
a = [[1 if i == '#' else 0 for i in STR()] for _ in range(h)]
s = 0
for i in range(h):
    s += sum(a[i])
y, x, cnt = func(0, 0, 0)
if y == h - 1 and x == w - 1 and cnt == s:
    print('Possible')
else:
    print('Impossible')


Measured memory_bytes: 60396
class Bipartite_Matching():
    # n : 頂点数
    def __init__(self, n):
        self.match = [-1]*n
        self.used = [0]*n
        self.n = n
        self.edges = [[] for i in range(n)]

    # u→v のedgeを張る
    def add_edge(self, u, v):
        self.edges[u].append(v)

    # 増加路の判定
    def dfs(self, v):
        self.used[v] = 1
        for u in self.edges[v]:
            w = self.match[u]
            if w < 0 or (not self.used[w] and self.dfs(w)):
                self.match[v] = u
                self.match[u] = v
                return True
        return False

    # 最大マッチングの辺数を返す
    def bipartite_matching(self):
        ret = 0
        for v in range(self.n):
            if self.match[v] < 0:
                self.used = [0]*self.n
                if self.dfs(v):
                    ret += 1
        return ret


n = int(input())
BP = Bipartite_Matching(2*n)
red = [None]*n
for i in range(n):
    a, b = map(int, input().split())
    red[i] = (a, b)
blue = [None]*n
for i in range(n):
    c, d = map(int, input().split())
    blue[i] = (c, d)

# blue をすべて見て、redを探す
for i in range(n):
    c, d = blue[i]
    for j in range(n):
        a, b = red[j]
        if a < c and b < d:
            BP.add_edge(n+i, j)
            BP.add_edge(j, n+i)
ans = BP.bipartite_matching()
print(ans)

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

using namespace std;

int main()
{
  int N, A[100000], B[100000];

  cin >> N;
  int mx = 0;
  for(int i = 0; i < N; i++) {
    cin >> A[i] >> B[i];
    mx = max(mx, A[i]);
  }
  for(int i = 0; i < N; i++) {
    if(mx == A[i]) {
      cout << mx + B[i] << endl;
    }
  }
}

Measured memory_bytes: 1024
import os
import sys
from collections import deque, defaultdict

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N = int(sys.stdin.buffer.readline())
X = list(map(int, sys.stdin.buffer.readline().split()))

ans = [None] * (N ** 2 + 1)
# 左にあるものから使う
P = list(sorted([(pos, i) for i, pos in enumerate(X, 1)]))

que = deque()
for p, i in P:
    ans[p] = i
    for _ in range(i - 1):
        que.append(i)

for p in range(1, N ** 2 + 1):
    if ans[p] is not None:
        i = ans[p]
        for _ in range(N - i):
            que.append(i)
    else:
        if not que:
            break
        ans[p] = que.popleft()


def is_ok(ans, que):
    if que:
        return False
    for a in ans[1:]:
        if a is None:
            return False
    counts = defaultdict(int)
    C = [0]
    for a in ans[1:]:
        counts[a] += 1
        C.append(counts[a])
    for i, x in enumerate(X, 1):
        if C[x] != i:
            return False
    return True


if is_ok(ans, que):
    print('Yes')
    print(*ans[1:])
else:
    print('No')


Measured memory_bytes: 15908
# coding: utf-8
# Here your code !

dataCount = int(input())
while dataCount > 0:
    employeeSalesList = []
    for _ in range(dataCount):
        dataList = input().split(" ")
        employeeId, price = int(dataList[0]), int(dataList[1]) * int(dataList[2])
        found = False
        for data in employeeSalesList:
            if data[0] == employeeId:
                data[1] += price
                found = True
        if not found:
            employeeSalesList.append([employeeId, price])

    answerList = [data[0] for data in employeeSalesList if data[1] >= 1000000]
    if answerList:
        print("\n".join(map(str, answerList)))
    else:
        print("NA")

    dataCount = int(input())

Measured memory_bytes: 7772
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <queue>
 
using namespace std;
 
#define pb(n)	push_back(n)
#define mp(n,m) make_pair(n,m)
#define fi 	first
#define se 	second
#define all(r) (r).begin(),(r).end()

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const int IMAX=((1<<30)-1)*2+1;
const double EPS=1e-10;
//int mod=1000000007;



int main(){
	ll n,ans=0;
	while(cin>>n){
		if(n==0)break;
		ans=0;
		while(1){
			if(n==1)break;
			if(n%2==0)n/=2;
			else n=n*3+1;
			ans++;
		}
		cout<<ans<<endl;
	}
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
#define repe(i,n) for (int i = 0; i <= (n); ++i)
#define repe1(i,n) for (int i = 0; i <= (n); ++i)
#define all(x) (x).begin(),(x).end()
#define pb(x) push_back(x)
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
typedef long long ll;
const int INF = 1e9;
const ll mod = 1000000007;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a * b / gcd(a, b);}

ll pow_kai(ll a, ll n) {
    ll x = 1;
    while(n > 0) {
        if(n&1) {
            x = x*a;
        }
        a = a*a;
        n >>= 1;
    }
    return x;
}

int main() {
    int a,b,c;
    cin >> a >> b >>c;
    set<int> hoge;
    hoge.insert(a);
    hoge.insert(b);
    hoge.insert(c);
    if (hoge.size() == 2) {
        cout << "Yes" << "\n";
    } else {
        cout << "No" << "\n";
    }
}

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

using namespace std;

#define inf 1<<30
#define llong long long
#define usd unsigned
#define pqueue priority_queue
#define mp make_pair
#define pb push_back
#define fn fill_n
typedef pair<int, int> P;
typedef struct data{
	int now;
	int cost;
}data;
int nw[9] = {0, 1, 0, -1, -1, 1, 1, -1, 0};
int nh[9] = {1, 0, -1, 0, 1, 1, -1, -1, 0};
int a,b,c,d, A[100], B[100], C[100][100], D[100][100][100];
string s, t, r;




int main(){
	cin >> a;
	b = 0;
	for(int i = 1; i <= a; i++){
		if(i % 2 == 0) continue;
		c = 0;
		for(int j = 1; j <= i; j++){
			if(i%j == 0) c++;
		}
		if(c == 8) b++;
	}
	cout << b << endl;

	return 0;
}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define REP(i,s,n) for(int i=s; i<(n); ++i)
#define ALL(n) begin(n),end(n)
using ll = long long;
const ll INF = numeric_limits<ll>::max();


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

    ll R_cnt = 0, G_cnt = 0, B_cnt = 0;
    REP(i, 0, N){
        if (S[i] == 'R')
            ++R_cnt;
        else if (S[i] == 'G')
            ++G_cnt;
        else 
            ++B_cnt;
    }

    ll sum = R_cnt * G_cnt * B_cnt;

    char i_str, j_str, k_str;
    REP(i, 0, N - 2){
        i_str = S[i];
        REP(width, 1, (N - 1 - i) / 2 + 1) {
            j_str = S[i + width];
            k_str = S[i + width + width];
            if (i_str != j_str && i_str != k_str && j_str != k_str)
                --sum;
        }
    }

    cout << sum << endl;

    return 0;
}


Measured memory_bytes: 3620
package main

import "fmt"

func main(){
	var b float64
	var a,c int64
	//var a,t int64
	fmt.Scan(&a,&b)
	c = int64(float64(b*100)+0.5)
	//sum := a*int64(b)
	//sum += a*(int(b*100-int64(b)*100)/100)
	//t = int64(b*100)-int64(b)*100
	fmt.Println(int64(a*c)/100)
	//fmt.Println(int64(a*int64(b))+int64(int64(a*t)/100))
}


Measured memory_bytes: 1752
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7


def main():
    n, m, q = MAP()
    abcd = ZIP(q)

    def ascending(X):
        for i in range(1, n):
            if A[i - 1] > A[i]:
                return False
        return True

    def point(A):
        tot = 0
        for a, b, c, d in abcd:
            if A[b - 1] - A[a - 1] == c:
                tot += d
        return tot

    def forward(A):
        # Mより小さい最後の桁
        k = None
        for i in reversed(range(n)):
            if A[i] < m:
                k = i
                break
        if k is not None:
            A[k] += 1
            for j in range(k + 1, n):
                A[j] = A[k]
        else:
            A[0] = INF

    # 昇順列を巡回する
    A = [1] * n
    ans = 0
    while ascending(A):         # O(N)
        # print(A)
        p = point(A)
        if ans <= p:
            ans = p
        forward(A)
    print(ans)

    return


if __name__ == '__main__':
    main()


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

#define ll long long

int main(){
    int a,b,c,d;

    cin >> a >> b >> c >> d;

    if(a*b > c*d){
        cout << a*b << endl;
    }
    else{
        cout<<c*d <<endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
const long long INF = 1LL << 60; 

int main()
{
  ll N; cin >> N;
  ll A[N+10]; rep(i,N) cin >> A[i];
  sort(A, A+N);
  bool ans = false;
  rep(i,N)
  {
    if(A[i] == A[i+1]) ans = true;
  }

  if(ans) cout << "NO" << endl;
  else cout << "YES" << endl;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#include<sstream>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
#define mod 1000000007
#define all(v) v.begin(),v.end()
#define loop(i,a,b) for(i=(int)a;i<(int)b;i++)
#define revloop(i,a,b) for(i=(int)a;i>=(int)b;i--)
#define stloop(it,v) for(it=v.begin();it!=v.end();++it)
#define ii pair<int,int>
#define mp make_pair
#define pb push_back
#define ll long long int
#define PI acos(-1.0)
#define f first
#define s second
#define rs resize
int main()
{  std::ios::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);
   int n;
   cin>>n;
   cout<<800*n - (n/15)*200;
   return 0;
}


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

int main(){
  int n,a,b;
  int x[100006];
  int i;
  ll ans = 0;

  scanf("%d %d %d", &n, &a, &b);
  for(i = 0;i < n;i++) scanf("%d", &x[i]);

  ll t;
  for(i = 0;i < n - 1;i++){
    t = x[i + 1] - x[i];
    if(t*a >= b) ans += b;
    else ans += t*a;
  }

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

  return 0;
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
int main()
{

    long long n,x;
    cin>>n;
    long long cnt=0,a=0;
    for(int i=0;i<n;i++)
    {
        cin>>x;
        if(x==a+1)
        {
            cnt++;
            a=a+1;
        }
    }

    if(cnt==0)cout<<-1;
    else cout<<n-cnt;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll lft[200005] , rgt[200005] , n , a[200005];
ll dp[200005][32];
const ll inf = 1e15;
ll solve(ll id ,ll x)
{
        if(x >= 17) return inf;
        if(id == n + 1) {
                return 0;
        }
        if(dp[id][x] != -1) return dp[id][x];
        ll mup = 1LL;
        for(ll i=0;i<x;i++) mup = mup*4;
        mup = mup * a[id-1];
        ll cnt = 0;
        ll cur = a[id];
        while(mup > cur) {
                cur = cur * 4; cnt++;
        }
        if(cnt <= 15){
        return dp[id][x] = solve(id+1, cnt) + cnt;

        }else {
                return dp[id][x] = solve(id+1, 15) + cnt + (cnt-15)*(n-id);
        }
}
ll ans[200005];
ll ans2[200005];
int main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL); cout.tie(NULL);
        cin >> n;
        for(ll i=1;i<=n;i++) cin >> a[i];
        for(ll i=2;i<=n;i++) {
                lft[i] = 0;
                ll cnt = 0;
                ll x = a[i];
                ll y = a[i-1];
                while(x < y) {
                        x = x*4;
                        cnt++;
                }
                lft[i] = cnt + cnt;
        }
        for(ll i = n-1; i>=1;i--) {

                rgt[i] =0;
                ll x = a[i] * 2;
                ll y = a[i+1];
                ll cnt = 0;
                while(x < y) {
                        x = x * 4;
                        cnt++;
                }
                rgt[i] = cnt + cnt + 1;
        }
        memset(dp,-1,sizeof dp);
        for(ll i=2;i<=n;i++) {
                for(ll j=0;j<=15;j++) {
                        ll  y= solve(i, j);
                        if(j==0) ans[i] = y + y;
                }
        }
        for(ll i=1;i<=n;i++) a[i] = a[i] * 2;
        memset(dp,-1,sizeof dp);
        reverse(a+1, a+n+1);
        for(ll i=2;i<=n;i++) {
                for(ll j=0;j<=15;j++) {
                        ll y = solve(i + 1,j);
                        if(j==0){
                                ans2[i] += y + y + (n-i+1);
                        }
                }
        }
        ll ret = 1e14;
        for(ll i=1;i<=n;i++) {
                ret = min(ret , ans[i + 1] + ans2[n+1-i + 1]);
        }
        cout << ret << endl;
        return 0;
}


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

char getPartner(char ch) {
  string left  = "()iw";
  string right = ")(iw";
  
  return left[right.find(ch)];
}

int main() {
  string str;
  int ret = 0;
  getline(cin, str);
  
  for(int i=0; i<=(str.size()-1)/2; i++) {
    if(str[i] != getPartner(str[str.size()-1-i])) ret++;
  }
  
  cout << ret << endl;
  
  return 0;
}

Measured memory_bytes: 1184
#include "bits/stdc++.h"

using namespace std;

#define int long long
#define ll long long
typedef pair<int, int> P;
#define mod 1000000007
#define INF (1LL<<60)

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl



signed main() {

	int N, x;
	int a[2001];
	cin >> N >> x;
	int ans = INF;
	rep(i, N) {
		cin >> a[i];
		ans += a[i];
	}


	int m[2001];
	rep(i, N) m[i] = a[i];

	// k: 魔法の回数
	for (int k = 0; k < N; k++) {
		rep(i, N) {
			int idx = i - k;
			if (idx < 0) idx += N;
			m[i] = min(m[i], a[idx]);
		}

		int s = 0;
		rep(i, N) s += m[i];
		s += x * k;

		ans = min(ans, s);

	}


	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void)
{
    long long h,n,a,k=0;
    cin>>h>>n;
    while(n--)
    {
        cin>>a;
        k+=a;
    }
    if(k>=h)
    {
        printf("Yes");
    }
    else{
        printf("No");
    }
    return 0;
}


Measured memory_bytes: 256
s = input()
t = input()

dp = [[0 for i in range(3010)] for j in range(3010)]

for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j], dp[i][j+1])
        
ans = ""
i = len(s)
j = len(t)
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans = s[i-1] + ans
        i -= 1
        j -= 1

print(ans)

Measured memory_bytes: 120028
// 043.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>

using namespace  std;

int main()
{
    int a, b, c;
	cin >> a >> b >> c;

	bool is_equal =
		a == b && a != c ||
		a == c && a != b ||
		b == c && b != a;
	cout << (is_equal ? "Yes" : "No");
}



Measured memory_bytes: 768
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

S = input()

flag = 0
for i in range(1, len(S)): #len(S)-1までに見つからないとあふれる
  if 'C' in S[:i]:
    if 'F' in S[i:]:
      print('Yes')
      exit()
print('No')



Measured memory_bytes: 38384
#include<bits/stdc++.h>
using namespace std;
#define FS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long int
#define ld long double
#define pb push_back
#define bp __builtin_popcount
#define sz size()
#define ff first
#define ss second
#define vll vector<ll>
#define vbool vector<bool>
#define vpll vector<pair<ll,ll>>
#define pll pair<ll,ll>
#define vllv vector<vector<ll>>
#define setpri(x) cout<<setprecision(x)<<fixed;
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define yesr {cout<<"YES"<<endl;return;}
#define nor {cout<<"NO"<<endl;return;}
// getline (std::cin,name);
ll MOD=1e9+7;
ll ceil1(ll n,ll x){if(n%x==0)return n/x; else return (n/x)+1;}
ll gcd(ll a,ll b){return __gcd(a,b);}
ll lcm(ll a,ll b){return (max(a,b)/gcd(a,b))*min(a,b);}
ll pow1(ll n,ll k,ll mm){
    if(k==0)return 1;
    if(k%2==0)return (pow1((n%mm)*(n%mm),k/2,mm))%mm;
    return ((n%mm)*(pow1((n%mm)*(n%mm),k/2,mm)%mm))%mm;
}
ll pow2(ll n,ll k){ll ans=1;
    while(k>0){
        if(k%2==1)ans=ans*n;n=n*n;k/=2;
    }return ans;
}
ll modinv(ll n,ll mod){
    return pow1(n,mod-2,mod);
}
bool func(pair<ll,ll> &a,pair<ll,ll> &b ){
    if(a.ff != b.ff)return a.ff < b.ff;
    return a.ss > b.ss;
}
void solve(){
    ll i,j,k,l,n,m,x,y,z,r;
	
	cin>>n;
	
	vll a(n+1);
	
	for(i=1;i<=n;i++){
		cin>>a[i];
	}
	map<ll,ll> mp,mp1;
	for(i=1;i<=n;i++){
		mp[a[i]+i]++;
		mp1[a[i]-i]++;
	}
	ll ans=0;
	for(i=1;i<=n;i++){
		ans+=mp[i-a[i]];
		ans+=mp1[-i-a[i]];
	}
	cout<<ans/2<<endl;
	
	
	
	
	
}
int main(){
    FS;
    ll i,j,k,n,m,x,y,z,q;
    q=1;
    // cin>>q;
    while(q--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 50132
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <unordered_map>
#include <map>
#include <set>
using namespace std;

typedef pair<int,int> P;

int main(int argc, char const *argv[]) {
  int n;
  int M = 30000;
  cin>>n;
  vector<int> p(n), a(n), b(n);
  vector<P> ps(n);
  for(int i=0;i<n;++i)cin>>p[i];
  for(int i=0;i<n;++i){
    a[i] = M*i+1;
    b[i] = M*(n-i-1)+1;
  }
  for(int i=0;i<n;++i){
    a[p[i]-1]+=i;
  }
  for(int i=0;i<n;++i){
    cout<<a[i]<<" ";
  }
  cout<<endl;
  for(int i=0;i<n;++i){
    cout<<b[i]<<" ";
  }
  cout<<endl;
  return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define pb push_back
int dy[]={0, 0, 1, -1, 1, 1, -1, -1};
int dx[]={1, -1, 0, 0, 1, -1, -1, 1};

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define mp make_pair
#define fi first
#define sc second
ll n,m;
int main(){
	cin >> n >> m;

	if(n == 1 && m == 1) {
		cout << 1 << endl;
	}else if(n == 1) {
		cout << m - 2 << endl;
	}else if(m == 1) {
		cout << n - 2 << endl;
	}else{
		cout << (n - 2) * (m - 2) << endl;
	}
	return 0;
}


Measured memory_bytes: 256
import sys

M, D = map(int,input().split())
c_list = []
m_list = []

if D>=22:
    for k in range(22,D+1):
        k_str = str(k)
        d10 = int(k_str[0])
        d1  = int(k_str[1])
        m = d10*d1
        if d1>=2:
            m_list.append(m)

else:
    print(0)
    sys.exit()

for i in range(M+1):
    c = m_list.count(i)
    c_list.append(c)

print(sum(c_list))


Measured memory_bytes: 3064
#pragma GCC optimize("O3")
#pragma GCC target ("sse4")

#include "bits/stdc++.h"
#include "ext/pb_ds/tree_policy.hpp"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/rope"

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for(int i = 0; i < (a); ++i)
#define pb push_back
#define mp make_pair
#define sz(x) (int)x.size()
#define f first
#define s second

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

struct custom_hash 
{
    static uint64_t splitmix64(uint64_t x) 
    {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const 
    {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
int m, d;
int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> m >> d;
    set<int> ans;
    for(int i = 1; i <= d; ++i)
    {
        int tmp = ((i%10) * (i/10));
        if(tmp >= 1 && tmp <= m && i/10 >= 2 && i%10 >= 2) ans.insert(i);
    }
    cout << sz(ans);
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#define FOR(i,a,b) for(int i=a;i<b;i++)

int main(){
	char A[100],B[100];
	int ans = 0;
	scanf("%s %s",A,B);
	if(strlen(A) > strlen(B)) ans = 1;
	if(strlen(A) < strlen(B)) ans = -1;
	if(strlen(A) == strlen(B)){
		FOR(i,0,strlen(A)){
			if(A[i] > B[i]){ ans = 1;  break; }
			if(A[i] < B[i]){ ans = -1; break; }
		}
	}
	if(ans == 1)  printf("GREATER\n");
	if(ans == -1) printf("LESS\n");
	if(ans == 0)  printf("EQUAL\n");
}

Measured memory_bytes: 128
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<pii, pii> state;
typedef vector<vector<ll>> matrix;

int r, c;
string g[1005];
int dp[1005][1005];
int dx[4]{-1,0,1,0};
int dy[4]{0,1,0,-1};

void solve() {
  cin >> r >> c;
  for(int i = 0; i < r; i++) cin >> g[i];
  queue<pii> q;
  for(int i = 0; i < r; i++) {
    for(int j = 0; j < c; j++) {
      if(g[i][j] == '#') {
        dp[i][j] = 0;
        q.push({i, j});
      }
      else dp[i][j] = 1e9;
    }
  }
  int ret = 0;
  while(!q.empty()) {
    pii curr = q.front();
    q.pop();
    ret = dp[curr.first][curr.second];
    for(int k = 0; k < 4; k++) {
      int nx = curr.first + dx[k];
      int ny = curr.second + dy[k];
      if(nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
      if(dp[nx][ny] != 1e9) continue;
      dp[nx][ny] = 1 + dp[curr.first][curr.second];
      q.push({nx, ny});
    }
  }
  cout << ret << "\n";
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  solve();
}


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

int main() {
  string ABCD;
  cin >> ABCD;
  for (int i = 0; i < 8; i++) {
    int tmp = stoi(ABCD.substr(0, 1));
    string ans = ABCD.substr(0, 1);
    for (int j = 0; j < 3; j++) {
      if (i >> j & 1) {
        tmp += stoi(ABCD.substr(j+1, 1));
        ans += "+"; ans += ABCD.substr(j+1, 1);
      } else {
        tmp -= stoi(ABCD.substr(j+1, 1));
        ans += "-"; ans += ABCD.substr(j+1, 1);
      }
    }
    if (tmp == 7) {
      cout << ans << "=7" << endl;
      return 0;
    }
  }
}

Measured memory_bytes: 256
# include <bits/stdc++.h>
# define sz(x) (int)((x).size())
# define F first
# define S second
# define pb push_back
# define ub upper_bound
# define lb lower_bound
# define all(x) x.begin(), x.end()
# define pqueue priority_queue
# define mset multiset
# define umap unordered_map
# define Speed() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
# define rep(i,n) for(int i=0;i<n;++i)
# define forn(i,n) for(int i=1;i<=n;++i)
# define lr(i,l,r) for(int i=l;(l>r?i>=r:i<=r);(l>r?--i:++i))

using namespace std;

template<class T> void umin(T &a,T b){a=min(a,b);}
template<class T> void umax(T &a,T b){a=max(a,b);}

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

const int dx[]={1,0,-1,0,-1,-1,1,1},dy[]={0,1,0,-1,-1,1,-1,1}; 
const int mod = 1e9+7;
const ll N = 2e5+4;

ll n,m,k,a[N],prefA[N],prefB[N],b[N];

bool check(ll x){
	for(int i=0;i<=n;++i){
		ll j=k;
		bool ok=0;
		if(i){
			if(prefA[i]<=k){
				j-=prefA[i];
				ok=1;
			}
		}
		ll l=1,r=m,ans=0;
		if(j>=prefB[1]){
			while(l<=r){
				ll m=(l+r)/2;
				if(prefB[m]<=j){
					ans=m;
					l=m+1;
				}
				else r=m-1;
			}		
		}
		if(ans+(ok?i:0)>=x)return 1;
	}
	return 0;
}

void solve(){
	cin>>n>>m>>k;
	forn(i,n){
		cin>>a[i];
		prefA[i]=prefA[i-1]+a[i];
	}
	forn(i,m){
		cin>>b[i];
		prefB[i]=prefB[i-1]+b[i];
	}
	ll l=0,r=n+m,ans=0;
	while(l<=r){
		ll m=(l+r)/2;
		if(check(m)){
			ans=m;
			l=m+1;
		}
		else r=m-1;
	}
	cout<<ans;
}

int main(){
	Speed();
	int T=1; 
	//cin>>T;	
	while(T--)
		solve();
	return 0;
}

Measured memory_bytes: 9868