akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include <algorithm>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define print(s) cout << s << endl
#define acc(v) accumulate(v.begin(), v.end(), 0)
#define cinv(n, v) rep(i, n) cin >> v[i]

using namespace std;
const int INF = 1e9;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vint;
typedef vector<string> vstr;
typedef vector<char> vchar;
const ll LINF = 1e18;
const ll MOD = 1e9 + 7;
int x_pos[4] = {1, 0, -1, 0}, y_pos[4] = {0, 1, 0, -1};
int ctoi(char c)
{
	if (c >= '0' && c <= '9')
	{
		return c - '0';
	}
	return 0;
}

char upper(char c)
{
	return c - 0x20;
}

char lower(char c)
{
	return c + 0x20;
}

void unique_vector(vector<int> &v)
{
	sort(all(v));
	v.erase(unique(all(v)), v.end());
}

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val)
{
	std::fill((T *)array, (T *)(array + N), val);
}

//ユークリッドの互除法
//最大公約数
ll gcd(ll x, ll y)
{
	if (y == 0)
		return x;
	return gcd(y, x % y);
}

//最小公倍数
ll lcm(ll x, ll y)
{
	ll g = gcd(x, y);
	return x / g * y;
}

ll myPow(ll x, ll n, ll m)
{
	if (n == 0)
		return 1;
	if (n % 2 == 0)
		return myPow(x * x % m, n / 2, m);
	else
		return x * myPow(x, n - 1, m) % m;
}

//k!
ll facctorialMethod(ll k)
{
	ll sum = 1;
	for (ll i = 1; i <= k; ++i)
	{
		sum *= i;
		sum %= MOD;
	}
	return sum;
}

//nCr
ll permutationMethod(ll n, ll r)
{
	ll n_sum, r_sum;
	r = n - r;
	n_sum = facctorialMethod(n);
	r_sum = facctorialMethod(r);
	return n_sum / r_sum;
}

// mod. m での a の逆元 a^{-1} を計算する
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

ll pow_kai(int a, int n)
{ //aのn乗を計算します。
	ll x = 1;
	while (n > 0)
	{ //全てのbitが捨てられるまで。
		if (n & 1)
		{ //1番右のbitが1のとき。
			x = (x * a) % MOD;
		}
		a = (a * a) % MOD;
		n >>= 1; //bit全体を右に1つシフトして一番右を捨てる。
	}
	return x % MOD;
}

int main()
{
	int k, s;
	cin >> k >> s;
	int ans = 0;
	for (int i = 0; i <= k; i++)
	{
		for (int l = 0; l <= k; l++){
			if(i+l <=s && s- (i+l) <= k){
				ans++;
			}
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>
 
using namespace std;
 
#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(i=0;i<n;i++)
#define loop(i,a,n) for(i=a;i<n;i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
 
typedef vector<int> vi;
typedef pair<int,int> pii;
 
#define MAX_N 100000
 
int parent[MAX_N];
int ran[MAX_N];
 
void init(int n)
{
  int i;
  rep(i,n){
    parent[i]=i;
    ran[i]=0;
  }
}
int find(int x)
{
  if(parent[x]==x)
    return x;
  else
    return parent[x]=find(parent[x]);
}
 
void unite(int x,int y)
{
  x=find(x);
  y=find(y);
  if(x==y)return;
 
  if(ran[x]<ran[y])
    parent[x]=y;
  else{
    parent[y]=x;
    if(ran[x]==ran[y])ran[x]++;
  }
}
 
vi lan[100005];
 
int main()
{
  int i,j;
  int n,m;
  cin>>n>>m;
  //  vi lan(m);                                   
  rep(i,n){
    int k,l;
    cin>>k;
    rep(j,k){
      cin>>l;
      l--;//0indexed                               
      lan[l].push_back(i);//0indexed               
    }
  }
 
  init(n);
  rep(i,m){
    rep(j,lan[i].size())
      unite(lan[i][0],lan[i][j]);
  }
  bool ans=true;
  rep(i,n){
    if(find(parent[0])!=find(parent[i]))
      ans=false;
  }
  if(ans)cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
}

Measured memory_bytes: 4736
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
using vll = vector<vl>;
using Pll = pair<ll, ll>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(v) v.begin(), v.end()
#define sz(x) ((int) x.size())
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
const int MOD = 1e9+7;
const ll INF = 2e15;
template<class T> void print(const T& t){ cout << t << endl; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

int main(){
  ll n;
  cin>>n;
  bool ans=false;
  ll count=0;
  rep(i,n){
    ll a,b;
    cin>>a>>b;
    if(a==b){
      count++;
    }
    else{
      count=0;
    }
    if(count==3){
      ans=true;
    }
  }
  cout<<(ans?"Yes":"No")<<endl;
}


Measured memory_bytes: 3628
#include<cstdio>
#include<climits>
using namespace std;
static const int MAX_N = 100000;
 
int n, q;
 
int n_;
int laz[4 * MAX_N];
 
void init(){
    n_ = 1;
    while(n_ < n) n_ *= 2;
    for(int i = 0; i < 2 * n_ - 1; i++){
        laz[i] = -1;
    }
    laz[0] = INT_MAX;
}
void prop(int len, int k){
    if(laz[k] == -1) return;
    if(2 * k + 1 < 2 * n_ - 1){
        laz[2 * k + 1] = laz[k];
        laz[2 * k + 2] = laz[k];
    }
}
void update(int a, int b, int x, int k, int l, int r){
    if(r <= a || b <= l) return;
    if(a <= l && r <= b){
        laz[k] = x;
        return;
    }
    prop(r - l, k);
    laz[k] = -1;
    update(a, b, x, 2 * k + 1, l, (l + r) / 2);
    update(a, b, x, 2 * k + 2, (l + r) / 2, r);
}
         
int find(int index, int len, int k){
    if(laz[k] != -1) return laz[k];
    if(2 * k + 1 >= 2 * n_ - 1) return laz[k];
    int diff = ((index % len < len / 2) ? 1 : 2);
    return find(index, len / 2, 2 * k + diff);
}
 
int main(){
    scanf("%d %d", &n, &q);
    init();
    for(int i = 0; i < q; i++){
        int op;
        scanf("%d", &op);
        if(op == 0){
            int s, t, x;
            scanf("%d %d %d", &s, &t, &x);
            update(s, t + 1, x, 0, 0, n_);
        }else if(op == 1){
            int index;
            scanf("%d", &index);
            printf("%d\n", find(index, n_, 0));
        }
    }
    return 0;
}


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

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a.at(i);
  }
  for (int i = n - 1; i > 0; i--) {
    cout << a.at(i) << " ";
  }
  cout << a.at(0) << endl;
}


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

int main() {
  int p,q,r;
  cin>>p>>q>>r;
  int ans=min(p+q,q+r);
  ans=min(ans,r+p);
  cout<<ans;
}
      

Measured memory_bytes: 256
# 方針
# 頂点uからvに至る際に通る辺のリストをe[u][v]とする。
# M個の制約からl個(l>=1)選んだ際に，いずれの制約も満たさないために白く塗るべき辺の個数を考える。
# これは,uiからviに至る際に通る辺のリストの和集合の要素の数。

from collections import deque

N = int(input())
adj = [[] for i in range(N + 1)] # 1-ind
ve = {} # 両端の頂点の番号⇒辺の番号
for i in range(1, N) : # 1-ind
    a, b = map(int,input().split())
    adj[a].append(b); adj[b].append(a)
    ve[(a, b)] = ve[(b, a)] = i
# print(adj) #DB
# print(ve) #DB

# 頂点iからスタートし，葉に行き着くまでの通過頂点とそれまでに通過した辺を記録
l = [[set() for j in range(N + 1)] for i in range(N + 1)]
q = deque()
for i in range(1, N + 1):
    r = [False] * (N + 1)
    q.append(i); r[i] = True
    while q:
        u = q.popleft()
        for v in adj[u]:
            if r[v]:
                continue
            l[i][v].update(l[i][u])            
            l[i][v].add(ve[(u, v)])
            q.append(v)
            r[v] = True
# print(l) #DB
'''
for i in range(1, N + 1):
    for j in range(i, N + 1):
        print(i, j, l[i][j])
'''
M = int(input())
c = [set()]
for i in range(1, M + 1): # 1-ind
    u, v = map(int,input().split())
    c.append((u, v))

ans = 2 ** (N - 1)
for k in range(1, 1 << M): # 制約0個の場合を除外 ※初期値で考慮することもできそう
    V = set()
    d = 0 # 考慮する制約の個数
    for i in range(1, M + 1):
        if k >> (i - 1) & 1:
            d += 1
            u, v = c[i]
            V |= l[u][v]
    # print(k, V)
    temp = 2 ** (N - 1 - len(V))
    # print(d, temp)
    if d % 2 == 1:
        ans -= temp
    elif d % 2 == 0:
        ans += temp

print(ans)

Measured memory_bytes: 46684
N,L = gets.split.map(&:to_i)
sum = 0
ajis2 = []
N.times do |i|
    aji = L + (i+1) -1
    sum += aji
    ajis2 << aji.abs
end
puts sum > 0 ? sum - ajis2.min : sum + ajis2.min

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

#define INF 1000010000
#define nl '\n'
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pdd pair<double,double>
#define all(c) (c).begin(), (c).end()
#define SORT(c) sort(all(c))
#define sz(c) (c).size()
#define rep(i,n) for( int i = 0; i < n; ++i )
#define repi(i,n) for( int i = 1 ; i <= n; ++i )
#define repn(i,n) for( int i = n - 1 ; i >= 0 ; --i )
#define repf(j,i,n) for( int j = i ; j < n ; ++j )
#define die(s) {std::cout << s << nl;}
#define dier(s) {std::cout << s; return 0;}
#define vi vector<int>
typedef long long ll;

using namespace std;

bool f(vi & v , int & n , int & k , int t){
	vi dp(555555 , 0);
	vi mn(555555 , -1);
	
	dp[0] = 1;
	rep(i , n){
		if(i != t){
			rep(j , k){
				if(dp[j] && mn[j] != i){
					if(j + v[i] < k){
						dp[j + v[i]] = 1;
						if(mn[j + v[i]] == -1){
							mn[j + v[i]] = i;
						}
					}
				}
			}
		}
	}

	repf(i , k - v[t] , k){
		if(i >= 0 && dp[i]){
			return 1;
		}
	}

	return 0;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.precision(0); 
	
	int n , k;
	cin >> n >> k;
	
	vi v(n);
	rep(i , n){
		cin >> v[i];
	}
	
	SORT(v);
	
	int l = 0 , r = n - 1;

	
	if(f(v , n , k , 0))dier(0);
	if(!f(v , n , k , n - 1))dier(n);
	
	while(r - l > 1){
		int mid = (r + l) / 2;
		if(f(v , n , k , mid)){
			r = mid;
		}else{
			l = mid;
		}
	}

	dier(l + 1);

	return 0;
}

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

#define endl '\n'

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n , x , t;
    cin >> n >> x >> t;
    int ans = 0;

    ans = (n / x) + ((n % x) ? 1 : 0);

    cout << (ans * t);


    return 0;
}

Measured memory_bytes: 3608
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);

		int num = in.nextInt();
		int[] array = new int[num];

		for(int cnt = 0; cnt < num; cnt++){

			array[cnt] = in.nextInt();

		}

		for(num = num-1; num >= 0; num--) {

			if(num != 0) {

				System.out.print(array[num] + " ");

			}else {

				System.out.println(array[num]);
			}
		}

	}

}

Measured memory_bytes: 26256
#include <algorithm>
#include <iostream> //入出力
#include <stdio.h>
#include <map>
#include <set>
#include <string>
#include <math.h> //算術演算子
#include <vector>
#include <cstdlib>
#include <queue>
#include <stack>
#include <list>
#include <iomanip> //小数点以下を表示させる(setprecision())
//#include <bits/stdc++.h>
using namespace std;
typedef long long ll; //64bit型

#define debug(x) cerr << x << " " \
                      << "(L:" << __LINE__ << ")" << '\n'
#define PRINT(V)                                   \
        {                                          \
                for (int i = 0; i < V.size(); i++) \
                {                                  \
                        cout << V[i] << " ";       \
                }                                  \
                cout << endl;                      \
        }

int gcd(int a, int b)
{
        return b ? gcd(b, a % b) : a;
}

int main()
{
        //input->compute->output//
        int A, B;
        cin >> A >> B;

        cout <<max({A*B,A+B,A-B}) << endl;

        return 0;
}


Measured memory_bytes: 256
package main

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

var scanner = bufio.NewScanner(os.Stdin)

func main() {
	scanner.Split(bufio.ScanWords)

	n, k := nextInt(), nextInt()
	d := make([]int, k)
	a := make([][]int, k)
	for i := 0; i < k; i++ {
		d[i] = nextInt()
		a[i] = make([]int, d[i])
		for j := 0; j < d[i]; j++ {
			a[i][j] = nextInt()
		}
	}

	m := make(map[int]bool)
	for i := range d {
		for _, v := range a[i] {
			m[v] = true
		}
	}
	fmt.Println(n - len(m))
}

func next() string {
	scanner.Scan()
	return scanner.Text()
}

func nextInt() int {
	i, err := strconv.Atoi(next())
	if err != nil {
		fmt.Println(err)
	}
	return i
}


Measured memory_bytes: 1868
from itertools import product
N = int(input())
result  = 0
for n in range(1, 10):
    for p in product("357", repeat=n): # n個使った
        if len(set(p)) != 3 :
            continue
        elif int(''.join(p))<=N :
            result += 1
            continue
        
print(result)

Measured memory_bytes: 3060
#include <stdio.h>
int main(){
  int a,i,n;
  int L[7];
  while (1){
    scanf("%d",&n);
    if (n==0)break;
    for (i=0;i<7;i++)
        L[i]=0;
    for (i=0;i<n;i++){
      scanf("%d",&a);
      if (a>60) a=60;
      L[a/10]++;
    }
    for (i=0;i<7;i++)
      printf("%d\n",L[i]);

  }
  return 0;
}

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

#define int long long
#define ll long long
#define pb push_back
#define mp make_pair
#define f(i,a,n) for(int i=a ; i<(int)n ; i++)
#define rf(i,n,a) for(int i=n ; i>=a ; i--)
#define F first
#define S second
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()
#define fast ios:: sync_with_stdio(false),cin.tie(nullptr);

typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef vector<pii> vpi;

const int inf = 1e9;
const int inf64 = 1e18;
const int MOD = inf + 7;

void solve(){
   int s,w;
   cin >> s >> w;
   cout << (w >= s ? "unsafe" : "safe");
}

int32_t main(){
   fast;
   int t = 1;
//   cin >> t;
   while(t--)  solve();   
}

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

int main()
{
  string mind;
  cin>>mind;
  int ans=0;
  for(int i=0 ; i<mind.length() ; ++i)
  {
  	if(mind[i]=='+')
    ++ans;
  	else
    --ans;
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cmath>
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <queue>
using namespace std;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define REP(i,n) for(ll i=0;i<n;i++)
#define REPR(i,n) for(ll i=n-1;i>=0;i--)

typedef long long ll;
#define INF 1e18

int main(){
	ll x; cin>>x;
	ll a=0;
	a=x/500;
	x-=a*500;
	ll b=0;
	b=x/5;
	cout<<a*1000+b*5<<endl;
	return 0;
}


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

int k;
string s;
vector<string> ls;

int main() {
  cin >> s >> k;
  for(int i = 0; i < s.size(); ++i)
    for(int j = 1; j + i <= s.size() && j < 6; ++j)
      ls.push_back(s.substr(i, j));
  sort(ls.begin(), ls.end());
  ls.erase(unique(ls.begin(), ls.end()), ls.end());
  cout << ls[k - 1] << endl;
  return 0;
}

Measured memory_bytes: 1660
import java.util.*;
import java.io.PrintWriter;

public class Main{
	static int[] c=new int[26];
	static int[] lastD=new int[26];
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		int d=sc.nextInt();
		for(int i=0; i<26; i++){
			c[i]=sc.nextInt();
		}
		int[][] s=new int[d][26];
		for(int i=0; i<d; i++){
			for(int j=0; j<26; j++){
				s[i][j]=sc.nextInt();
			}
		}
		int sati=0;
		for(int i=1; i<=d; i++){
			int t=sc.nextInt()-1;
			lastD[t]=i;
			sati+=s[i-1][t];
			sati-=subSati(i);
			System.out.println(sati);
		}
	}
	static int subSati(int d){
		int ret=0;
		for(int i=0; i<26; i++){
			ret+=c[i]*(d-lastD[i]);
		}
		return ret;
	}
}


Measured memory_bytes: 46660
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) _repi(i,0,n)
#define _repi(i,a,b) for(ll i=a;i<b;++i)
#define rep(...) _overload3(__VA_ARGS__,_repi,_rep)(__VA_ARGS__)
#define _rrepi(i,a,b) for(ll i=b-1;i>=a;i--)
#define _rrep(i,n) _rrepi(i,0,n)
#define rrep(...) _overload3(__VA_ARGS__,_rrepi,_rrep)(__VA_ARGS__)
#define sum(...) accumulate(range(__VA_ARGS__),0)
#define _range(i) (i).begin(),(i).end()
#define _rangek(i,k) (i).begin(),(i).begin()+k
#define range(...) _overload3(__VA_ARGS__,a,_rangek,_range)(__VA_ARGS__)
#define LINF (ll)1000000000000000000
#define MOD (ll)1000000007
#define INF (int)1000000007
#define Yes(i) out(i?"Yes":"No")
#define YES(i) out(i?"YES":"NO")
#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;in(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;in(__VA_ARGS__)
#define vec(type,name,size) vector<type> name(size);
#define VEC(type,name,size) vector<type> name(size);in(name)
struct aaa{aaa(){cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(15);};}aaaaaaa;
inline void in() {}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec);
template<typename T,typename L>
istream& operator >> (istream& is, pair<T,L>& p);
template<typename T>
ostream& operator << (ostream& os, vector<T>& vec);
template<typename T,typename L>
ostream& operator << (ostream& os, pair<T,L>& p);
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){for(T& x: vec) is >> x;return is;}
template<typename T,typename L>
istream& operator >> (istream& is, pair<T,L>& p){is >> p.first;is >> p.second;return is;}
template<typename T>
ostream& operator << (ostream& os, vector<T>& vec){os << vec[0];rep(i,1,vec.size()){os << ' ' << vec[i];}return os;}
template<typename T,typename L>
ostream& operator << (ostream& os, pair<T,L>& p){os << p.first << " " << p.second;return os;}
template <class Head, class... Tail>
inline void in(Head&& head,Tail&&... tail){cin>>head;in(move(tail)...);}
template <class T>
inline void out(T t){cout<<t<<'\n';}
template <class Head, class... Tail>
inline void out(Head head,Tail... tail){cout<<head<<' ';out(move(tail)...);}


int main(){
    INT(a);
    a%=7;
    if(a==0)out("thu");
    else if(a==1)out("fri");
    else if(a==2)out("sat");
    else if(a==3)out("sun");
    else if(a==4)out("mon");
    else if(a==5)out("tue");
    else out("wed");
}















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

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef long long ll;

const long long INF = 1LL << 60;

int main()
{
    ll N, M;
    cin >> N >> M;

    vector<ll> A(N);
    rep(i, N) cin >> A[i];

    map<ll, ll> mod;
    ll tmp = 0;
    mod[0]++;
    rep(i, N) {
        tmp += A[i];
        mod[tmp % M]++;
    }

    ll res = 0;
    for (auto itr = mod.begin(); itr != mod.end(); itr++) {
        res += itr->second * (itr->second - 1) / 2;
    }

    cout << res << endl;


    return 0;
}

Measured memory_bytes: 4992
n, q = map(int, input().split())
string = input()
cumsum = [0,0]
for i in range(1, len(string)):
    res = cumsum[-1]
    if string[i-1] == 'A' and string[i] == 'C':
        res += 1
    cumsum.append(res)

mat = [list(map(int, input().split())) for _ in range(q)]
for l, r in mat:
    ans = cumsum[r] - cumsum[l]
    print(ans)

Measured memory_bytes: 30688
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <bitset>
#include <cmath>
#include <string>
#include <iterator>
#define FI first
#define SE second
#define PF push_front
#define PB push_back
#define POF pop_front
#define POB pop_back
#define MA make_pair
#define ll long long
#define VE vector<int>
#define VP vector<pair<int,int> >
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ROF(i,a,b) for(int i=b-1;i>=a;i--)
#define YES(i) cout<<(i?"YES":"NO")<<endl
#define Yes(i) cout<<(i?"Yes":"No")<<endl
using namespace std;
//
const int INF=1e9+7;
const int mod=1e9+7;
//
int main(){
  int W,H,N,X,Y,NX,NY;
  cin>>W>>H>>N;
  int ans=0;
  cin>>NX>>NY;
  FOR(i,1,N){
    cin>>X>>Y;
    if(NX<=X&&NY<=Y){
      ans+=max(X-NX,Y-NY);
    }else if(X<=NX&&Y<=NY){
      ans+=max(NX-X,NY-Y);
    }else{
      ans+=abs(NX-X)+abs(NY-Y);
    }
    NX=X;NY=Y;
  }
  cout<<ans<<endl;
  return 0;
}


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

int main(){
	int n,m,d[1000],t[1000],type[4][100],c[4][100];
	cin>>n>>m;
	for(int i=0;i<m;i++){
		cin>>d[i]>>t[i];
	}
	for(int i=0;i<m;i++){
		if(d[i]==1){
			type[d[i]][1]=1;
			goto Exit1;
		}
	}
	type[1][1]=1;
	type[2][1]=1;
	type[3][1]=1;
	
Exit1:
	for(int i=1;i<=3;i++){
		if(type[i][1]!=1){
			type[i][1]=0;
		}
	}
	type[1][2]=0;
	type[2][2]=0;
	type[3][2]=0;
	for(int i=2;i<=n;i++){
		for(int j=0;j<m;j++){

			if(d[j]==i){
				type[t[j]][2]=type[t[j]][1];
				type[t[j]][1]=0;
				for(int k=1;k<=3;k++){
					if(t[j]!=k){
						for(int l=1;l<=2;l++){
						type[t[j]][1] += type[k][l];
						type[k][l]=0;
						}
					}
				}
				goto Exit2;
			}

		}
		memset(c,0,sizeof(c));
		for(int k=1;k<=3;k++){
			for(int l=1;l<=3;l++){
				if(k==l){
					c[l][2] += type[k][1];
				}
				else{
					c[l][1] += type[k][1]+type[k][2];
				}
			}
		}
		for(int k=1;k<=3;k++){
			type[k][1]=c[k][1];
			type[k][2]=c[k][2];
		}
Exit2:
		for(int j=1;j<=3;j++){
			for(int k=1;k<=2;k++){
				type[j][k]=type[j][k]%10000;
			}
		}
	}
	cout<<(type[1][1]+type[1][2]+type[2][1]+type[2][2]+type[3][1]+type[3][2])%10000<<endl;
	return 0;
}

Measured memory_bytes: 1172
n = input()
dic = {'A':0,'B':1,'C':2,'D':3,'E':4,'F':5,'G':6,'H':7,'I':8,'J':9,'K':10,'L':11,'M':12,\
       'N':13,'O':14,'P':15,'Q':16,'R':17,'S':18,'T':19,'U':20,'V':21,'W':22,'X':23,'Y':24,'Z':25}
if n in dic:
  print('A')
else:
  print('a')

Measured memory_bytes: 9132
#![allow(non_snake_case)]
fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let Q: usize = 998244353;
    let N:usize = sc.read();
    // if N == 1{
    //     let t:usize = sc.read();
    //     if t == 0{
    //         println!("1");
    //     }else{
    //         println!("0");
    //     }
    //     return
    // }
    let V:Vec<usize> = sc.vec(N);
    let mut now:usize = 1;
    let mut VC:Vec<usize> = vec![0;N];
    for i in 0..N{
        VC[V[i]] += 1;
    }
    if V[0] != 0{
        println!("0");
        return        
    }
    if VC[0] != 1{
        println!("0");
        return
    }

    // let mut check:usize = 0;
    
    // for i in 0..N{
    //     // if VC[i] >= N{
    //     //     println!("0");
    //     //     return
    //     // }
    //     if VC[i] == 0{
    //         println!("0");
    //         return
    //     }
    //     check += VC[i];
    //     if check == N{
    //         break;
    //     }
    // }
    // // for i in 0..4{
    // //     println!("{} {}",i, VC[i] );
    // // }
    let mut ans :usize = 1;
    for i in 1..N{
        for _ in 0..VC[i]{
            ans *= now;
            ans %= Q;
        }
        now = VC[i];
        // if now == 0{
        //     break;
        // }
    }

    println!("{}", ans%Q);
}

pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n')
            .take_while(|&b| b != b' ' && b != b'\n')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
        .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}



Measured memory_bytes: 6396
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define INF 1000000021
#define MOD 1000000007
#define pb push_back
#define sqr(a) (a)*(a)
#define M(a, b) make_pair(a,b)
#define F first
#define S second
#define all(x) (x.begin(), x.end())
#define deb(x) cerr << #x << " = " << x << '\n'
#define N 222222

using namespace std;
using namespace __gnu_pbds;

typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

const ld pi = 2 * acos(0.0);
template<class T> bool umin(T& a, T b){if(a>b){a=b;return 1;}return 0;}
template<class T> bool umax(T& a, T b){if(a<b){a=b;return 1;}return 0;}
template<class T, class TT> bool pal(T a, TT n){int k=0;for(int i=0;i<=n/2;i++){if(a[i]!=a[n-i-1]){k=1;break;}}return k?0:1;}

//int month[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};

int main()
{
	ll A, B, K;
	ll x = 1, y = 0;
	cin >> K >> A >> B;
	if(A >= B || A >= K)
		return cout << K + 1, 0;
	ll ans = B;
	ll k = K;
	K -= A + 1;
	cout << max(k + 1,ans + (K / 2)*(B - A) + (K % 2 != 0));

	





	getchar();
	getchar();
	return 0;
	//ios::sync_with_stdio(false);
	//cin.tie(0);
}

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

ls = len(s)
lt = len(t)
match = -1

for i in range(ls-lt+1):
    for j in range(lt):
        if s[i+j] == t[j] or s[i+j] == '?':
            pass
            #continueはここで処理が終わってしまう
        else:
            break
            
        if j == lt - 1:
            match = i
        
for i in range(ls):
    if s[i] == '?':
        s[i] = 'a'
        
for i in range(lt):
    s[match+i] = t[i]
        
if match < 0:
    print("UNRESTORABLE")
else:
    print(''.join(s))

Measured memory_bytes: 3064
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <complex>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define rep(i, n) for (ll i = 0; i < (n); ++i)

using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;
using vll = vector<ll>;
using vP = vector<P>;
using vvll = vector<vector<ll>>;
using vvP = vector<vector<P>>;

const ll INF = 1LL << 32;

int main() {
  ll n, t;
  cin >> n >> t;
  //ll x = t / 2;

  vll lst(n);
  vll mins(n);

  //ll cnt = 0;
  ll minv = LONG_LONG_MAX;
  map<ll, ll> mp;
  ll key = 0;
  for (ll i = 0; i < n; i++) {
    ll tmp;
    cin >> tmp;
    chmax(key, tmp - minv);
    mp[tmp - minv]++;
    chmin(minv, tmp);
  }

  ll ans = mp[key];
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 8064
#include <bits/stdc++.h>
    #define fio ios_base::sync_with_stdio(false), cin.tie(NULL)
    #define ll long long int
    #define ld long double
    #define f(a, b) for (ll i = a; i < b; i++)
    #define in(a, b) (b.find(a) != string::npos)
    #define X first
    #define Y second
    #define vi vector<int>
    #define fill(a, x) memset(a, x, sizeof(a))
    #define pb push_back
    #define pf push_front
    #define mp make_pair
    #define all(v) v.begin(), v.end()
    #define el "\n"
    const ll M = 1e9 + 7;
    using namespace std;

    int main() {
    fio;
    int n=5;
    int a[n]={0};
    ll sm=0;
    vector<pair<int,int>> v;
    for(int i=0;i<n;i++){
        cin>>a[i];
        v.pb(mp((10-a[i]%10)%10,i));
    }
    sort(all(v));
    for(int i=0;i<n;i++){
        sm+=a[v[i].Y];
        if(sm%10!=0 && i!=n-1){
            while(sm%10!=0)sm++;
        }
    }
    cout<<sm<<el;
    return 0;
    }


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

int main(void)
{
  int n, m, a[51], b[51], c[51], d[51], i, j, min, ans;

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

  for(i = 0; i < m; i++)
    scanf("%d %d", &c[i], &d[i]);

  for(i = 0; i < n; i++){
    min=500000000;
    for(j = 0; j < m; j++){
      if(min > abs(a[i]-c[j])+abs(b[i]-d[j])){
	min = abs(a[i]-c[j])+abs(b[i]-d[j]);
	ans = j+1;
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}


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

int main(){
    long long int N;
    cin >> N;
    int ans = 0;
     for(int i=2;i<1000010;i++){
        int cur = 0;
        while (N % i == 0) {
            cur++;
            N /= i;
        }
        for(int j=1;j<=cur;j++) {
            ans++; cur -= j;
        }
    }
    if(N>1) ans++;
    cout << ans << endl;

	return 0;

}





Measured memory_bytes: 3616
using System;

class ABC_169_C
{
    static void Main(string[] args)
    {
        string[] input = Console.ReadLine().Split(' ');
        long A = long.Parse(input[0]);
        float B = float.Parse(input[1]);

        long LB = (((long) (B * 1000)) + 5) /10;

        Console.WriteLine((A*LB)/100);
    }
}

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

int d[14];
bool used[14];
bool solve(int p, int cnt, bool r) {
	bool ok = false;
	if (cnt == 3) {
		int f = -1, s = -1;
		rep(i, 14) {
			if (!used[i]) {
				if (f == -1)f = d[i];
				else if (s == -1)s = d[i];
				else ok = true;
			}
		}
		if (!ok) {
			if (f == s)return true;
			return false;
		}
		ok = true; cnt = 0;
	}
	rep(i, 14) {
		if (!used[i] && (ok || (r&&d[i] == p + 1) || (!r&&d[i] == p))) {
			used[i] = true;
			if (solve(d[i], cnt + 1, r))return true;
			if (ok) {
				if (solve(d[i], cnt + 1, !r))return true;
			}
			used[i] = false;
		}
	}
	return false;
}
int main(){
	while (1) {
		int cnt[10]{};
		rep(i, 13) {
			if (!~scanf("%1d", &d[i]))return 0;
			cnt[d[i]]++;
		}
		bool flag = false;
		for (int i = 1; i <= 9; i++) {
			if (cnt[i] >= 4)continue;
			d[13] = i;
			memset(used, 0, sizeof(used));
			if (solve(0, 3, 0)) {
				if (flag)printf(" ");
				printf("%d", i);
				flag = true;
			}
		}
		if (!flag)printf("0");
		printf("\n");
	}
}

Measured memory_bytes: 3072
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class T, class U> using Pa = pair<T, U>;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;

template<class T>
class BinaryTree{
private:
    struct Node{
        T val;
        Node *par;
        Node *left;
        Node *right;
    };
    Node *root;
    void insert(int x,Node* now){
        if(x < now->val){
            if(now->left != nullptr){
                insert(x,now->left);
            }else{
                now->left = new Node;
                now->left->val = x;
                now->left->left = nullptr;
                now->left->right = nullptr;
            }
        }else{
            if(now->right != nullptr){
                insert(x,now->right);
            }else{
                now->right = new Node;
                now->right->val = x;
                now->right->left = nullptr;
                now->right->right = nullptr;
            }
        }
    }
    void inorder_walk(Node* now,vec<T>& v){
        if(now->left!=nullptr) inorder_walk(now->left,v);
        v.push_back(now->val);
        if(now->right!=nullptr) inorder_walk(now->right,v);
    }
    void preorder_walk(Node* now,vec<T>& v){
        v.push_back(now->val);
        if(now->left!=nullptr) preorder_walk(now->left,v);
        if(now->right!=nullptr) preorder_walk(now->right,v);
    }
public:
    BinaryTree():root(nullptr){}
    void insert(T x){
        if(root==nullptr){
            root = new Node;
            root->val = x;
            root->left = nullptr;
            root->right = nullptr;
        }else{
            insert(x,root);
        }
    }

    vec<T> inorder_walk(){
        vec<T> res;
        inorder_walk(root,res);
        return res;
    }
    vec<T> preorder_walk(){
        vec<T> res;
        preorder_walk(root,res);
        return res;
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    BinaryTree<int> tree;
    int N;
    cin >> N;
    while(N--){
        string s;
        cin >> s;
        if(s=="insert"){
            int x;
            cin >> x;
            tree.insert(x);
        }else{
            auto res = tree.inorder_walk();
            int n = res.size();
            for(int i=0;i<n;i++) cout << " " << res[i];
            cout << "\n";
            res = tree.preorder_walk();
            n = res.size();
            for(int i=0;i<n;i++) cout << " " << res[i];
            cout << "\n";
        }
    }
}


Measured memory_bytes: 31288
function Main(input) {
	input = input.split("\n");
	var N = parseInt(input[0]);
	var M = new Array(5).fill(0);
	for(var i = 0; i < N; i++){
		switch(input[i+1][0]){
			case "M":
				M[0]++;
				break;
			case "A":
				M[1]++;
				break;
			case "R":
				M[2]++;
				break;
			case "C":
				M[3]++;
				break;
			case "H":
				M[4]++;
				break;
		}
	}
	var ans = 0;
	for(i = 0; i < 3; i++){
		for(var j = i+1; j < 4; j++){
			for(var k = j+1; k < 5; k++){
				ans += M[i] * M[j] * M[k];
			}
		}
	}
	console.log(ans);
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 30772
#include<bits/stdc++.h>
#pragma warning(disable:4996)
using namespace std;
using ll = long long;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int N;
int main() {
	cin >> N;
	long double N_test = (double)N;
	long double l = N_test / 4;
	long double r = N_test * 2 / 7;
	if (N % 4 == 0 || N % 7 == 0) {
		cout << "Yes" << endl;
	}
	else {
		int l_int = l;
		int r_int = r;
		if (l_int == r_int) {
			cout << "No" << endl;
		}
		else {
			cout << "Yes" << endl;
		}
	}

}


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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll

#define INF 1e16
#define mod 1000000007

ll N;
vector<ll> g[100010];
ll deg[100010];
vector<ll> vs;
ll resb[100010];

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

  cin>>N;
  vs.resize(N);
  rep(i,N-1){
    ll a,b;
    cin>>a>>b;
    a--;b--;
    g[a].push_back(b);
    g[b].push_back(a);
    deg[a]++;
    deg[b]++;
  }
  rep(i,N)cin>>vs[i];
  sort(all(vs));
  ll resa=0;
  rep(i,N-1)resa+=vs[i];

  queue<ll> que;
  rep(i,N){
    if(deg[i]==1)que.push(i);
  }
  rep(i,N){
    ll v=que.front(); que.pop();
    resb[v]=vs[i];
    deg[v]--;
    for(ll nv : g[v]){
      if(deg[nv]==0)continue;
      deg[nv]--;
      if(deg[nv]==1){
        que.push(nv);
      }
    }
  }
  cout<<resa<<endl;
  rep(i,N)cout<<resb[i]<<" ";
  cout<<endl;

  return 0;
}


Measured memory_bytes: 3328
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from math import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect
import heapq
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
#
# インデックス系
# int min_y = max(0, i - 2), max_y = min(h - 1, i + 2);
# int min_x = max(0, j - 2), max_x = min(w - 1, j + 2);
#
#
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
#mod = 998244353
INF = float('inf')
from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
    return int(readline())
a,b,x = readInts()
x /= a
import math
PI = math.pi
if x > a*b//2:
    print("{:.10}".format(math.atan2((a*b-x)*2, a*a)*180/PI))
else:
    print("{:.10}".format(math.atan2(b*b, x*2)*180/PI))


Measured memory_bytes: 10616
#include <iostream>
#include <vector>
#include <numeric>//accumulate(v.begin(), v.end(), 0);
#include <algorithm>//sort(v.begin(),v.end());
#include <string>//
#include <cmath>
#include <iomanip> //setprecision(2)
using namespace std;
#define ll long long
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

int main(){
        string s,t;
        int N;
        cin >> s;
        N=s.size();
        t =s[0];
        int sum=0;

        rep(i,1<<(N-1)){
                int a;
                sum=s[0]-'0';
                t=s[0];
                for(int j=0; j<N-1; j++) {
                        a=s[j+1]-'0';
                        if(i & (1<<j)) {
                                sum+=a;
                                t+='+';
                                t+=s[j+1];
                        }else{
                                sum-=a;
                                t+='-';
                                t+=s[j+1];
                        }
                }
                if(sum==7) {
                        cout << t << "=7" << endl;
                        break;
                }
        }
        return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;

int main() {
    int n, k;
    cin >> n >> k;
    ll res = k;
    for (int i = 1; i < n; i++) {
        res *= (k-1);
    }
    cout << res << endl;
}

Measured memory_bytes: 256
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,C=MI()
    XV=LLIN(N)
    DP1 = [0]*(N+1)
    DP2 = [0]*(N+1)
    before = 0
    for i,(x,v) in enumerate(XV):
        DP1[i+1]=DP1[i]+v-(abs(x-before))
        before = x
    before = C
    for i,(x,v) in enumerate(XV[::-1]):
        DP2[i+1]=DP2[i]+v-(abs(x-before))
        before = x
    ans = max(max(DP1),max(DP2))
    now = 0

    DP1_ = [d-XV[i][0] for i,d in enumerate(DP1[1:])]
    DP2_ = [d-(C-XV[~i][0]) for i,d in enumerate(DP2[1:])]
    for i in range(N-1):
        if(DP2_[i+1]<DP2_[i]):
            DP2_[i+1] = DP2_[i]
        if(DP1_[i+1]<DP1_[i]):
            DP1_[i+1] = DP1_[i]
    now1 = 0
    now2 = 0
    for i in range(N):
        idx = N-1-i
        # print(DP1[i],DP2_[idx])
        # print(DP2[i],DP1_[idx])
        ans = max(ans,DP1[i]+DP2_[idx])
        ans = max(ans,DP2[idx]+DP1_[i])
        # print(ans)
    # print(DP1)
    # print(DP2)
    # print(DP1_)
    # print(DP2_)
    print(ans)

if __name__ == '__main__':
    main()


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

using namespace std;

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

int main(){
	map<string,int> mp;
	ios::sync_with_stdio(false);
	string s;
	string a,b;
	b="";
	while (cin>>s){
		mp[s]++;
		if (s.length()>b.length()){
			b=s;
		}
	}
	int ma=0;
	for (auto ite=mp.begin();ite!=mp.end();ite++){
		if (ite->second > ma){
			ma = ite->second;
			a = ite->first;
		}
	}
	cout << a << " "<<b<<endl;
	return 0;
}

Measured memory_bytes: 3132
#include <bits/stdc++.h>
using namespace std;
const int64_t INF = 1000000000;

int main()
{
  int64_t N, a, ans = INF;
  cin >> N;
  for (int i = 0; i < N; i++)
  {
    cin >> a;
    int64_t cnt = 0;
    while (a % 2 == 0)
    {
      a /= 2;
      cnt++;
    }
    ans = min(ans, cnt);
  }
  cout << ans << endl;
}

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

using namespace std;

int main(){
  string n; cin >> n;
  vector<int> a;
  for(int i = 0; i < n.size(); i++){
    a.push_back(n[i]-'0');
  }
  reverse(a.begin(), a.end());
  vector<vector<int> > keta(a.size()+1, vector<int>(2, 0));
  keta[0][0] = a[0];
  keta[0][1] = 10 - a[0];
  for(int i = 1; i < a.size()+1 ; i++){
    keta[i][0] = min(keta[i-1][0] + a[i], keta[i-1][1] + 1 + a[i]);
    keta[i][1] = min(keta[i-1][0] + 10 - a[i], keta[i-1][1] + 9 - a[i]);
  }
  cout << keta[a.size()][0] << endl;
}


Measured memory_bytes: 59896
# # Make IO faster
# import sys
# input = sys.stdin.readline

# # get single (or) multiple str
# X = input()

# # get single int
# N = int(input())
# # get multiple int (e.g., 2)
# X, Y = map(int, input().split())
# # get multiple int (e.g., 2) for N lines
# XY = [list(map(int, input().split())) for _ in range(N)]

# from IPython import embed; embed(); exit();

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

print(eval(input().replace(",", " ")))


Measured memory_bytes: 27120
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
#define allR(v) v.rbegin(), v.rend()
#define PRINT(v) for (auto x : (v)) cout <<x <<" " ; cout <<endl;
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
typedef pair<int,int> Pi;
const ll MOD = 1000000007;
const ll INF = 10000000000000000;
const int inf = 1001001001;
vector<int> x4 = {0, 1, 0, -1}, x8 = {0, 1, 1, 1, 0, -1, -1, -1};
vector<int> y4 = {1, 0, -1, 0}, y8 = {1, 1, 0, -1, -1, -1, 0, 1};
template<class T> inline bool chmin(T& a, T b){if (a>b){a = b; return true;}return false;}
template<class T> inline bool chmax(T& a, T b){if (a<b){a = b; return true;}return false;}
template<class T> inline T powerM(T a,T b){if (b==0) return 1;
T tmp = powerM(a,b/2); if (b%2==0) return tmp*tmp%MOD; else return tmp*tmp%MOD*a%MOD; }
template<class T> inline T power(T a,T b,T m){ if (b==0) return 1;
  T tmp = power(a,b/2,m); if (b%2==0) return tmp*tmp%m; else return tmp*tmp%m*a%m; }
template<class T> inline T gcd(T a, T b){if (b==0) return a; return gcd(b, a%b);}
template<class T> inline T lcm(T a, T b){return a / gcd(a,b) * b;}
// ax+by=gcd(a,b)を解く
template<class T> inline T extgcd(T a,T b,T &x,T &y){if (b==0){x=1; y=0; return a;} T d=extgcd(b,a%b,y,x); y -= a/b*x; return d;}
void hey(){ cout <<"hey" <<endl; }

template<class T> struct edge { int to; T cost;};


int main() {
  int n; cin >>n;
  vector<ll> A(n); rep(i, n) cin >>A[i];
  sort(all(A));
  if (A[0] == 0){
    cout <<0 <<endl; return 0;
  }
  // 0は含まれていない
  ll res = 1;
  rep(i, n){
    ll a = A[i];
    if (res*a > 1000000000000000000){
      cout <<-1 <<endl; return 0;
    }else if (res*a < 0){
      cout <<-1 <<endl; return 0;
    }else if (res > res * a || a > res * a){
      cout <<-1 <<endl; return 0;
    }
    res *= a;
  }
  cout <<res <<endl;
}


Measured memory_bytes: 3996
#include <iostream>
using namespace std;
int main(){

  int x=0,y=0;
  
  while(x>=0 && y>=0){
    cin >>x>>y;
    if(x == 0 && y == 0)break;
    if(x>y){
      cout <<y<<" "<<x<<"\n";
    }
    else{
      cout <<x<<" "<<y<<"\n";
    }
  }
return 0;
}

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

using namespace std;

map<long long, long long> m;

long long Solve(long long a) {
	if (a == 1) return 1;
	if (m[a]) return m[a];
	return 1 + 2 * Solve(a / 2);
}

int main() {
	long long a; cin >> a;
	cout << Solve(a) << '\n';
	return 0;
}


Measured memory_bytes: 256
import sys
from functools import reduce
import copy
import math
from pprint import pprint
import collections
import bisect


sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def int_inputs(num_of_input):
    ins = [int(input()) for i in range(num_of_input)]
    return ins


def solve(inputs):
    X = int(inputs[0])
    r = X
    count = 0
    count += (r // 11) * 2
    r = r % 11
    if r > 6:
        count += 2
    elif r > 0:
        count += 1
    return count


def string_to_int(string):
    return list(map(int, string.split()))


if __name__ == "__main__":
    ret = solve(inputs(1))
    print(ret)


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

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
		if(ASB == "H H") Console.WriteLine("H");
		if(ASB == "H D") Console.WriteLine("D");
		if(ASB == "D H") Console.WriteLine("D");
		if(ASB == "D D") Console.WriteLine("H");
		
		
	}
	String ASB;
	public Sol(){
		ASB = rs();
	}

	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
	static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
	static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
}


Measured memory_bytes: 11092
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int N;
    scanf("%d", &N);
    
    vector<pair<int, int> > red;
    vector<pair<int, int> > blue;

    for (int i=0; i<N; i++){
        int a,b;
        scanf("%d %d", &a, &b);
        red.push_back({a,b});
    }
    for (int i=0; i<N; i++){
        int c,d;
        scanf("%d %d", &c, &d);
        blue.push_back({d,c});
    }

    sort(red.begin(), red.end());
    sort(blue.begin(), blue.end());

    //printf("red:");
    //for (int i=0; i<N; i++) printf("%d %d\n", red[i].first, red[i].second);
    
    //printf("blue:");
    //for (int i=0; i<N; i++) printf("%d %d\n", blue[i].first, blue[i].second);
    
    int cnt=0;

    for (int i=0; i<N; i++)
    {
        int trigger=101;
        for (int j=0; j<N; j++)
        {
            if (red[j].first < blue[i].second && red[j].second < blue[i].first)
            {
                trigger=j;
            }
        }
        //printf("trigger: %d\n", trigger);
        if (trigger>N-1) continue;

        cnt++;

        red[trigger] = pair<int, int> (1000, 1000);
    }
    
    printf("%d", cnt);

    return 0;
}

Measured memory_bytes: 256