akhauriyash/Code-Regression huggingface dataset:
import java.util.*;
class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner (System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		
		int temp = a ^ b;
		temp = temp ^ c;
		System.out.println(temp);
		sc.close();

	}

}

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

int main()
{
    string t;
    cin >> t;
    for (int i = 0; i < t.length(); i++)
    {
        if (t.at(i) == 'D' || t.at(i) == '?')
        {
            cout << 'D';
        }
        else
        {
            cout << 'P';
        }
    }
    cout << endl;
}

Measured memory_bytes: 3360
# 解説を見た

class Calc:
    def __init__(self, max_value, mod):
        """combination(max_value, all)"""
        fact = [-1] * (max_value + 1)
        fact[0] = 1
        fact[1] = 1
        for x in range(2, max_value + 1):
            fact[x] = x * fact[x - 1] % mod

        invs = [-1] * (max_value + 1)
        invs[max_value] = pow(fact[max_value], mod - 2, mod)
        for x in range(max_value - 1, 0, -1):
            invs[x] = invs[x + 1] * (x + 1) % mod
        # 逆元はこの求め方が速いらしい

        self.fact = fact
        self.invs = invs
        self.mod = mod

    def combination(self, n, r):
        if n - r < r:
            return self.combination(n, n - r)
        if r < 0:
            return 0
        if r == 0:
            return 1
        if r == 1:
            return n
        return self.fact[n] * self.invs[r] * self.invs[n - r] % self.mod


def main():
    MOD = 10 ** 9 + 7

    N = int(input())
    *A, = map(int, input().split())

    pos = [-1] * (N + 1)
    indices = None
    for i, a in enumerate(A):
        if pos[a] == -1:
            pos[a] = i
        else:
            indices = pos[a], i
            break

    width = indices[1] - indices[0] + 1
    # 重複要素を両端に持つような区間の長さ

    calc = Calc(max_value=N + 1, mod=MOD)

    for k in range(1, N + 1 + 1):
        res = (calc.combination(N + 1, k) - calc.combination(N + 1 - width, k - 1)) % MOD
        print(res)


if __name__ == '__main__':
    main()

# PxQxR
# PxRが重複

# 重複要素xの含まれる個数で場合分けをする

# xを含まない
# xを2個とも含む
# 一意

# xを1個含む場合でも、
# Qの要素を含む場合は、どっちのxを取ったか分かる

# Qの要素を含まないとき、どっちのxを取ったか分からない
# cmb(N+1,K)-cmb(PRの総和,K-1)


Measured memory_bytes: 20432
#include <bits/stdc++.h>
#define INF INT_MAX
using namespace std;
int dp[100005],h[100005];
int rec(int i,int n){
	if(i==n)return 0;
	if(dp[i]!=-1)return dp[i];

	         int  	x=i+1<=n?abs(h[i]-h[i+1])+rec(i+1,n):INF;
	          int  y=i+2<=n?abs(h[i]-h[i+2])+rec(i+2,n):INF; 
	            return dp[i]=min(x,y);
	          
}
int main() {
     int n,i;
     cin>>n;
     for(i=1;i<=n;i++){
     	cin>>h[i];
     }
     for(i=1;i<=n;i++){
     	dp[i]=-1;
     }
   int  ans=rec(1,n);
   cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 5760
#include <bits/stdc++.h> //C++の機能を「全て」読み込むための命令
#define rep(i,n) for(int i=0; i<(n); ++i)
#define cout(x) cout<<(x)<<endl
#define all(v) v.begin(), v.end()
using namespace std;
//型エイリアス
using vi = vector<int>;
using ll = long long;
using P = pair<int,int>;
using Mat = vector<vector<int>>;
const ll inf = 1e18;
const int N = 2e5+10;

int main(){
    int n;
    cin >> n;
    
    ll factorial=1;
    ll thr = 1e9;
    for(int i=1;i<=n;++i){
        factorial = (factorial*i)%(thr +7);
    }
    cout<<factorial<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
const int INF=1e9,MOD=1e9+7;
const long long LINF=1e18;
using namespace std;
#define int long long
//template
//main
signed main(){
  int N;cin>>N;
  int ans=0;
  int mi=1;
  int z;cin>>z;ans+=z-1;
  for(int i=1;i<N;i++){
    int a;cin>>a;
    if(a<=mi+1){
      mi=max(a,mi);
      continue;
    }
    ans+=(a-1)/(mi+1);
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 256
//============================================================================
// Name        : abc101.cpp
// Author      : sep
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <cmath>
#include <ctime>
#include <functional>
#include <algorithm>
#include <vector>

using namespace std;

inline void main101A() {

	int n = 0;
	int i;
	string s;

	cin >> s;

	for (i = 0; i < s.length(); i++)
		if (s[i] == '-') {
			--n;
		} else {
			++n;
		}

	cout << n;

}

inline void main101B() {

	long long int n;
	int i;
	long long int temp;
	long long int sum = 0;

	cin >> n;
	temp = n;

	for (i = 0; temp > 0; i++) {
		sum += temp % 10;
		temp /= 10;
	}

	if (n % sum == 0) {
		cout << "Yes";
	} else {
		cout << "No";
	}

}

inline void main101C() {

	long long int n, k;
	long long int *a;
	int i;
	long long int p;
	long long int res = 0;
	cin >> n >> k;

	a = new long long int[n];

	for (i = 0; i < n; i++) {
		cin >> a[i];
		if (a[i] == 1) {
			p = i;
		}
	}

	if (p > 0) {

		res += p / (k - 1);
		if (p % (k - 1) > 0)
			res++;
	}

	res += (n - p - 1) / (k - 1);
	if ((n - p - 1) % (k - 1) > 0)
		res++;

	cerr << (n - p - 1) % (k - 1) << endl;
	cerr << p % (k - 1) << endl;

	if (((n - p - 1) % (k - 1) + p % (k - 1) <= k - 1)
			&& ((n - p - 1) % (k - 1) != 0) && (p % (k - 1) != 0))
		res--;

	cout << res;

	delete[] a;

}

inline void main101D() {

	long long int k;
	long long int i;
	long long int res = 0;
	cin >> k;

	cout << res;

}

int main() {

#ifdef TEST
	struct timespec startTime, endTime;
	while (1) {
		clock_gettime(CLOCK_REALTIME, &startTime);
#endif

		main101C();

#ifdef TEST
		cout << flush;
		cerr << flush;
		cerr << endl << "Elapsed Time:";
		clock_gettime(CLOCK_REALTIME, &endTime);
		if (endTime.tv_nsec < startTime.tv_nsec) {
			cerr << endTime.tv_sec - startTime.tv_sec - 1 << "."
					<< endTime.tv_nsec + 1000000000 - startTime.tv_nsec << "s"
					<< endl;
		} else {
			cerr << endTime.tv_sec - startTime.tv_sec << "."
					<< endTime.tv_nsec - startTime.tv_nsec << "s" << endl;
		}

		cerr << endl;
	}
#endif

	return 0;
}


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

int main(){
  int n;
  cin >> n;
  bool ans=true;
  vector<string> w(n);
  for(int i=0;i<n;i++){
    cin >> w[i];
  }
  for(int i=0;i<n-1;i++){
    if(w[i].back()!=w[i+1].front()){
      ans=false;
      break;
    }
  }
  sort(w.begin(),w.end());
  for(int i=0;i<n-1;i++){
    if(w[i]==w[i+1]){
      ans=false;
      break;
    }
  }
  if(ans){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;
import java.util.stream.*;

public class Main {
	private static BufferedReader br = null;
	
	public static void main(String[] args) {
		String n = read(1)[0];
		
		for (int i = 0; i < n.length(); i++) {
			System.out.print(n.charAt(i) == '1' ? '9' : '1');
		}
		
		System.out.println();
	}
	
	private static String[] read(int len) {
		List<String> strList = new ArrayList<>();
		
		try {
			if (br == null) {
				br = new BufferedReader(new InputStreamReader(System.in));
			}
			
			for (int i = 0; i < len; i++) {
				strList.add(br.readLine());
			}
		} catch (IOException e) {
		}
		
		return strList.toArray(new String[0]);
	}
	
	private static void close() {
		try {
			if (br != null) {
				br.close();
			}
		} catch (IOException e) {
		}
	}
}


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

/* typedef */
/* long系 */
typedef long long ll;   // long long
typedef long double ld; // long double
/* vector系 */
typedef vector<int> vi;                    // intのvector
typedef vector<double> vd;                 // doubleのvector
typedef vector<ll> vll;                    // llのvector
typedef vector<ld> vld;                    // ldのvector
typedef vector<vector<int>> vvi;           // intの2次元vector
typedef vector<vector<double>> vvd;        // doubleの2次元vector
typedef vector<vector<ll>> vvll;           // llの2次元vector
typedef vector<vector<ld>> vvld;           // ldの2次元vector
typedef vector<pair<int, int>> vi_i;       // i_iのvector
typedef vector<pair<double, double>> vd_d; // d_dのvector
typedef vector<pair<ll, ll>> vl_l;         // l_lのvector
typedef vector<pair<ld, ld>> vld_ld;       // ld_ldのvector
typedef vector<string> vs;                 // stringのvector
/* pair系 */
typedef pair<int, int> i_i;       // int同士のpair
typedef pair<double, double> d_d; // double同士のpair
typedef pair<ll, ll> l_l;         // ll同士のpair
typedef pair<ld, ld> ld_ld;       // ld同士のpair

/* define */
#define all(v) v.begin(), v.end() // コンテナ全体
#define PI (acos(-1))             // 円周率pi

/* stringstream */
stringstream ss;
stringstream init_ss; // save default formatting

/* upper, lower */
struct ToUpper
{
    char operator()(char c)
    {
        return toupper(c);
    }
};
struct ToLower
{
    char operator()(char c)
    {
        return tolower(c);
    }
};

/* main */
void Main(void)
{
    string s;
    cin >> s;
    int max = 0;
    for (int i = 0; i < s.size(); i++)
    {
        int j = i;
        int tmp = 0;
        while (j != s.size())
        {
            if (s[j] != 'A' && s[j] != 'C' && s[j] != 'G' && s[j] != 'T')
                break;
            else
                tmp++;
            j++;
        }
        if (max < tmp)
            max = tmp;
    }
    cout << max << endl;
}

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

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
 
int main()
{
  int A,B,C,X,cnt;
  cin >> A >> B >> C >> X;
  for(int i=0;i<=X/50 && i<=A;i++){
    for(int j=0;j<=(X-500*i)/100 && j<=B;j++){
      if(500*i+100*j+50*C>=X){
        cnt++;
      }
    }
  }
  cout << cnt;
}

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

int main() {
    double L, v, w, h;
    cin >> L;

    v = L / 3;
    L = L - v;
    w = L / 2;
    L = L - w;
    h = L;

    printf("%.7f\n", v * w * h);
    return 0;
}


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

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

	scanf("%d%d%d", &a, &b, &c);
	if (a > b) tmp = a, a = b, b = tmp;
	if (b > c) {
		tmp = b, b = c, c = tmp;
		if (a > b) tmp = a, a = b, b = tmp;
	}
	printf("%d %d %d\n", a, b, c);
	return 0;
}


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

const int MAX = 102;
int H,W;
char Map[MAX][MAX];
int a[26] ={0};

int main()
{
    cin>>H>>W;

    for(int i = 1;i<=H;i++)
        for(int j = 1;j<=W;j++)
        {
            cin>>Map[i][j];
            a[Map[i][j]-'a']++;
        }
    if(H>W){ int temp = W;W = H;H = temp;}
    int x = H/2 ,y = W/2;
    int x1 ,x2,x4;
    x1 = x2 = x4 = 0;
    if(H==1)
    {
        x2 = y;
        x1 = W%2;
    }
    else
    {
        x4 = x*y;
        x2 = (H*W - x4*4)/2;
        x1 = H*W -x4*4-x2*2;
    }

    for(int i = 0;i<26;i++)
    {
        if(a[i]!=0)
        {
            if(H!=1)
            {
                x4 -= a[i]/4;
            a[i] %= 4;
            }

            x2 -= a[i]/2;
            a[i] %= 2;
            x1 -= a[i];
            a[i] = 0;
        }
        //cout<<x1<<" "<<x2<<" "<<x4<<endl;
    }

    if(x1==0&&x2==0&&x4==0)
    {
        cout<<"Yes"<<endl;
    }
    else cout<<"No"<<endl;;

    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
typedef struct 
{
  char mark;
  int number;
}card;

void bubblesort(card*,int);
void selectionsort(card*,card*,int);

int main(){
  int n,i,j,t;
   card detail[36],detail2[36];
  char a;
  

  scanf("%d",&n);
  
  for(i=0; i<n; i++)
    {
    scanf(" %c%c",&detail[i].mark,&a);
    detail[i].number = atoi(&a);
  }

  for(i=0; i<n; i++)
  detail2[i]=detail[i];
  bubblesort(detail,n);
  selectionsort(detail,detail2,n);
  return 0;
}
  

void bubblesort(card a[],int n){
  int i,j;
  card tmp;
  for(i=0;i<n;i++){
    for(j=n-1;j>i;j--){
      if(a[j].number<a[j-1].number){
	tmp=a[j];  //swap
	a[j]=a[j-1];
	a[j-1]=tmp;
      }
    }
  }

  for(i=0; i<n; i++){
    if(i>0)printf(" ");
    printf("%c%d",a[i].mark,a[i].number);
  }

  printf("\n");
  printf("Stable\n");    
}


void  selectionsort(card a[],card a2[],int n){
  int i,j,minj,count=0;
  card tmp;
  for(i=0; i<=n; i++){
    minj=i;
    for(j=i; j<n; j++){
      if(a2[j].number<a2[minj].number){
	minj=j;
      }
    }
    tmp=a2[i];
    a2[i]=a2[minj];
    a2[minj]=tmp;
}
  for(i=0; i<n; i++){
    if(i>0)printf(" ");
    printf("%c%d",a2[i].mark,a2[i].number);
  }
  printf("\n");

  for(i=0;i<n;i++){
    if(a[i].mark != a2[i].mark || a[i].number != a2[i].number){
      printf("Not stable\n");
      count=1;
      break;
    }
  }
  if(count == 0) printf("Stable\n");
  
}

 



Measured memory_bytes: 2104
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <string>
#include <utility>
#include <map>
using namespace std;
#define rep(i,n) for(int i=1;i<=(int)(n);i++)
#define Rep(i,n) for(int i=0;i<=(int)(n-1);i++)
typedef long long ll;
typedef map<int,int> mint;
typedef pair<int,int> pint;
typedef pair<ll,ll> pll;
int dx[]={-1,0,1,0};
int dy[]={0,-1,0,1};
int inf=1e9+1000;
ll infi=1e18+100;

int n;
int a[100005];
 
int main(){
	cin>>n;
	Rep(i,n) cin>>a[i];
	sort(a,a+n);
	reverse(a,a+n);
	int ans=0;
	Rep(i,n){
		if(abs(a[0]-2*ans)>abs(a[0]-2*a[i])){
			ans=a[i];
		}
	}
	cout<<a[0]<<" "<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 640
#include<iostream>
using namespace std;
int main(){
	int a;
	cin>>a;
	int flag =1;
	while(a>3){
		if(a%4==0||a%7==0||a%11==0){
			cout<<"Yes"<<endl;
			flag=0;
			break;
		}
		else a-=11;
	}
	if(flag) cout<<"No"<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <map>
#include <algorithm>
#include <cmath>
using namespace std;

int toInt(const string &s) {
	istringstream is(s);
	int N; is >> N;
	return N;
}

string toString(int num, int L) {
	int len = log10(num) + 1;
	ostringstream os;
	for(int i = 0; i < L - len; i++)
		os << "0";
	os << num;
	return os.str();
}

int main() {
	for(int a, l; cin >> a >> l, a || l;) {
		map<int, int> m;
		m[a] = 0;
		int ansi = -1, ansj = -1;
		int ans = -1;
		for(int i = 1; i <= 20; i++) {
			string s = toString(a, l);
			sort(s.begin(), s.end());
			int minv = toInt(s);
			sort(s.rbegin(), s.rend());
			int maxv = toInt(s);
			int next = maxv - minv;
			if(m.count(next)) {
				ansj = m[next];
				ansi = i;
				ans = next;
				break;
			}
			else {
				m[next] = i;
			}
			a = next;
		}
		cout << ansj << " " << ans << " " << ansi - ansj << endl;
	}
}

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

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

  vector<int> vec(N);
  for (int i = 0; i < N; i++) {
   cin >> vec.at(i);
  }

  int sum=0;
  for (int i = 0; i < N; i++) {
      sum+=vec.at(i);
  }
  
  sort(vec.begin(), vec.end());
  cout << N+(X-sum)/vec.at(0) << endl;
}

Measured memory_bytes: 256
/* C/C++ program to remove invalid parenthesis */
#include <bits/stdc++.h> 
using namespace std; 


int main() 
{ 
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)
    cin>>arr[i];
    vector<int> dp(n,INT_MAX);
    dp[0]=0;
    dp[1]=abs(arr[0]-arr[1]);
    for(int i=2;i<n;i++)
    {
        dp[i]=min((dp[i-1]+abs(arr[i]-arr[i-1])),(dp[i-2]+abs(arr[i-2]-arr[i])));
    }
  //  divide(n1,n2);
    cout<<dp[n-1];
	return 0; 
} 


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

#define debug(x) cerr << x << " = "(x) << endl;
#define ll long long
#define rep(i,x,y) for(int i=x;i<y;i++)
#define rel(i,x,y) for(int i=x-1;i>=y;i--)
#define all(x) x.begin(),x.end()

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    ll n; cin >> n;
    int a[n];
    rep(i,0,n) cin >> a[i];
    int rui[n];
    ll ans = 0;
    rui[0] = a[0];
    // + -の順
    if(rui[0]<=0){
        ans += abs(rui[0])+1;
        rui[0] = 1;
    }
    bool plus = false;
    rep(i,1,n){
        rui[i] = rui[i-1] +a[i];
        if(plus && rui[i]<=0){
            ans += abs(rui[i])+1;
            rui[i] = 1;
        }
        if(!plus && rui[i]>=0){
            ans += abs(rui[i])+1;
            rui[i] = -1;
        }
        plus ^= 1;
    }
    // - + の時
    ll tans = 0;
    rui[0] = a[0];
    if(rui[0]>=0){
        tans += abs(rui[0])+1;
        rui[0] = -1;
    }
    plus = true;
    rep(i,1,n){
        rui[i] = rui[i-1] +a[i];
        if(plus && rui[i]<=0){
            tans += abs(rui[i])+1;
            rui[i] = 1;
        }
        if(!plus && rui[i]>=0){
            tans += abs(rui[i])+1;
            rui[i] = -1;
        }
        plus ^= 1;
    }
    cout << min(ans,tans) << endl;
}

Measured memory_bytes: 1024
from heapq import heappush, heappop

class Dijkstra:
    def __init__(self, N):
        self.N = N # #vertices
        self.E = [[] for _ in range(N)]

    def add_edge(self, init, end, weight, undirected=False):
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
    
    def distance(self, s):
        INF = float('inf')
        E, N = self.E, self.N
        self.dist = dist = [INF] * N # the distance of each vertex from s
        self.prev = prev = [-1] * N # the previous vertex of each vertex on a shortest path from s
        dist[s] = 0
        n_visited = 0 # #(visited vertices)
        heap = []
        heappush(heap, (0, s))
        while heap:
            d, v = heappop(heap)
            if dist[v] < d: continue # (s,v)-shortest path is already calculated
            for u, c in E[v]:
                temp = d + c
                if dist[u] > temp:
                    dist[u] = temp; prev[u] = v
                    heappush(heap, (temp, u))
            n_visited += 1
            if n_visited == N: break
        return dist
    
    def shortest_path(self, t):
        P = []
        prev = self.prev
        while True:
            P.append(t)
            t = prev[t]
            if t == -1: break
        return P[::-1]
    
N, M, r = map(int, input().split())
dk = Dijkstra(N)
for _ in range(M):
    a, b, c = map(int, input().split())
    dk.add_edge(a, b, c)
dist = dk.distance(r)
for d in dist:
    if d == float('inf'): print('INF')
    else: print(d)


Measured memory_bytes: 90068
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <queue>
#include <list>
#include <unordered_map>
#include <algorithm>
#include <functional>
#include <iomanip> // std::std::setprecision(X)
#include <limits>  //std::numeric_limits<int>::max(), min()

typedef long long ll;


//---------------------------------------------------------------------------------------------------
namespace MyMod {
  typedef long long ll;
  constexpr ll mod = 1e9+7;
  ll power (ll e, ll x){
    if (x == 0) return 1LL; if (x % 2 != 0) return ((power(e, x-1) * e) % mod);
    ll temp = power(e, x / 2); return (temp * temp) % mod;
  }
  ll add ( ll a, ll b ) { return ((a%mod) + (b%mod))%mod; }
  ll sub ( ll a, ll b ) { return ( a%mod + mod - b%mod)%mod; }
  ll mul ( ll a, ll b ) { return ((a%mod) * (b%mod)) % mod; }
  ll div ( ll a, ll b ) { return ((a%mod) * power(b,mod-2)) % mod; }
};
//---------------------------------------------------------------------------------------------------


//---------------------------------------------------------------------------------------------------
constexpr ll mod = 1e9+7;
constexpr ll premax = 200020;
ll f[premax], rf[premax];

ll inv(ll x) {  return MyMod::power(x, mod-2); }
void init() {
  f[0] = 1;
  for(int i=1; i<premax; i++) f[i] = (f[i - 1] * i) % mod;
  rf[premax - 1] = inv(f[premax - 1]);
  for(int i=premax-2; i>=0; i--) rf[i] = (rf[i + 1] * (i + 1)) % mod;
}

ll C(int n, int k) {
  ll a = f[n]; // = n!
  ll b = rf[n-k]; // = (n-k)!
  ll c = rf[k]; // = k!
  ll bc = (b * c) % mod;
  return (a * bc) % mod;
}
//---------------------------------------------------------------------------------------------------

int main (void) {

  ll N, M; std::cin >> N >> M;

  init();

  ll tmp = M, ans = 1;
  for(int i=2; i<=tmp; i++) {
    ll cnt = 0;
    while(tmp%i==0){
      cnt++;
      tmp /= i;
    }
    ans *= C(cnt+N-1, cnt);
    ans %= MyMod::mod;
  }

  std::cout << ans << std::endl;

  return 0;
}

Measured memory_bytes: 3328
void main() {
    int n = readln.chomp.to!int;
    int[] t = readln.split.to!(int[]);
    int m = readln.chomp.to!int;
    int[] p = new int[m], x = new int[m];
    foreach (i; 0 .. m) {
        int[] tmp = readln.split.to!(int[]);
        p[i] = tmp[0], x[i] = tmp[1];
    }
    foreach (i; 0 .. m) {
        writeln(x[i] + t[0..p[i]-1].sum + t[p[i]..$].sum);
    }
}

import std.stdio;
import std.string;
import std.array;
import std.conv;
import std.algorithm;
import std.range;
import std.math;
import std.numeric;
import std.container;
import std.typecons;
import std.ascii;
import std.uni;

Measured memory_bytes: 256
// need
#include <iostream>
#include <algorithm>
// data structure
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <complex>
//#include <deque>
#include <valarray>
#include <unordered_map>
#include <array>
// stream
//#include <istream>
#include <sstream>
//#include <ostream>
#include <fstream>
// etc
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
//#include <chrono>
#include <random>
#include <numeric>
using namespace std;
char flag[400][400];
char table[400][400];
int H, W;

long white, black;
void dfs(int h, int w){
  	flag[h][w] = 1;
	if(table[h][w] == '.')
      white++;
  	else if(table[h][w] == '#')
      black++;
  	if(h > 0){
    	if((table[h][w] != table[h-1][w]) && (flag[h-1][w] != 1))
          dfs(h-1, w);
    }
  	if(h < H-1){
    	if((table[h][w] != table[h+1][w]) && (flag[h+1][w] != 1))
          dfs(h+1, w);
    }
  	if(w > 0){
    	if((table[h][w] != table[h][w-1]) && (flag[h][w-1] != 1))
          dfs(h, w-1);
    }
  	if(w < W-1){
    	if((table[h][w] != table[h][w+1]) && (flag[h][w+1] != 1))
          dfs(h, w+1);
    }
}
int main()
{
  long sum;
  cin >> H >> W;
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      cin >> table[i][j];
    }
  }
  sum = 0;
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      black = white = 0;
      if(flag[i][j] != 1){
      	dfs(i, j);
      	sum += black*white;
      }
    }
  }
  cout << sum << endl;
  
  return 0;
}

Measured memory_bytes: 13056
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=1010;
char s[maxn];
int n;
int a1,a2,a3,a4;
int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=1;i<=n;i++) a1|=(s[i]=='N'),a2|=(s[i]=='S'),a3|=(s[i]=='E'),a4|=(s[i]=='W');
	if(a1 && (!a2)){
		puts("No");return 0;
	}else if((!a1) && a2){
		puts("No");return 0;
	}else if((!a3) && a4){
		puts("No");return 0;
	}else if(a3 && (!a4)){
		puts("No");return 0;
	}
	puts("Yes");
	return 0;
}

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


int main(){
  int n;
  string s;
  cin >> n >> s;
  string ss = s;
  for(int i = 0; i < s.length(); i++){
    ss[i] = (s[i] - 'A' + n)%26 + 'A';
  }
  
  cout << ss;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define countof(array) (sizeof(array) / sizeof(array[0]))
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define rep2(i,n) for(int i = 1; i <= (n); ++i)
#define rrep2(i,n) for(int i = (n); i > 0; --i)
#define srep(i,s,n) for(int i = s; i < (n); ++i)
#define rsrep(i,s,n) for(int i = (n)-1; i >= s; --i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aall(a) (a), (a)+countof(a)//for array sorting
#define raall(a) (a), (a)+countof(a), greater<>()
#define show(x) cout<<#x<<" = "<<(x)<<endl;
#define vfind(v, a) find(all(v), a) != v.end()
#define yn(f) { if (f) puts("YES"); else puts("NO"); }
#define yns(f) { if (f) puts("Yes"); else puts("No"); }
#define show_ary(...) { cout<<#__VA_ARGS__<<" = "; for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define show_pair(...) cout<<#__VA_ARGS__<<" = "<<endl; for (const auto& x : (__VA_ARGS__)) { cout<<"  "<<x.fi<<" : "<<x.se<<endl; }
#define out_ary(...) { int n = (__VA_ARGS__).size(); rep(i, n) printf("%d%s", (__VA_ARGS__)[i], i != n-1 ? " " : "\n"); }
#define argmax(v) distance((v).begin(), max_element(all(v)))
#define argmin(v) distance((v).begin(), min_element(all(v)))
#define vmax(v) *max_element(all(v))
#define vmin(v) *min_element(all(v))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<P> vpair;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<string> vstr;
typedef vector<bool> vbool;
typedef vector<vint> vvint;
typedef vector<vll> vvll;
typedef vector<vstr> vvstr;
typedef vector<vbool> vvbool;
const ll LINF = 2000000000000000000ll;
const int INF = 1000000100;
const ll MOD = 1e9+7;


int main() {
    int n;
    cin >> n;
    vint a(n);
    rep(i, n) cin >> a[i];

    vint b(n);
    vpair bp(n);
    rep(i, n) {
        b[i] = -a[i]+i+1;
        bp[i] = make_pair(-a[i]+i+1, a[i]+i+1);
    }
    sort(all(b));
    sort(all(bp));

    ll ans = 0;
    rep(i, n) {
        ll num = 0;
        num -= lower_bound(all(b), bp[i].se) - b.begin();
        num += lower_bound(all(b), bp[i].se+1) - b.begin();
        ans += num;
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 6432
import java.util.Scanner;
public class Main{
 public static void main(String[] args){
   Scanner sc = new Scanner(System.in);
   int H = sc.nextInt();
   int W = sc.nextInt();
	int h = sc.nextInt();
	int w = sc.nextInt();

   
   System.out.println((H-h)*(W-w));
 }
}

Measured memory_bytes: 21844
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>

#define N 200000+10 
using namespace std;
long long a[N];
long long b[N];
int n;
int main()
{
	cin>>n;
	b[0]=0;
	long long ans=1e18;
	for(int i=1;i<=n;i++) 
	{
		cin>>a[i];
		b[i]+=b[i-1]+a[i];
	}
	for(int i=1;i<=n-1;i++)
	{
		long long sum2=b[n]-b[i];
		ans=min(ans,abs(b[i]-sum2));
	}
	cout<<ans<<endl;
	return 0;
}

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

typedef long long ll;
const int INF = 1e9;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n;
	cin>>n;
	string s;
	cin>>s;
	ll r, g, b;
	r = g = b = 0;
	for (char c: s){
		switch(c){
			case 'R': r++; break;
			case 'G': g++; break;
			case 'B': b++; break;
		}
	}
	ll extra = 0;
	for (int gap = 1; gap*2 < n; gap++) {
		for (int i = 0; i+gap*2 < n; i++) {
			if (s[i] != s[i+gap] && s[i] != s[i+gap*2] && s[i+gap] != s[i+gap*2])
				extra++;
		}
	}
	cout<<r*g*b-extra<<'\n';
	return 0;
}

Measured memory_bytes: 3648
from collections import defaultdict
n , m = map(int , input().split())
h  = list(map(int , input().split()))
dic = defaultdict(list)
for i in range(m):
	u , v = map(int , input().split())
	dic[u].append(v)
	dic[v].append(u)
ans = 0
for i in range(1, n+1):
	currh = h[i-1]
	f = 1
	if i in dic: 
		for obs in dic[i]:
			if i == obs: continue
			if h[obs-1] >= currh:
				f = 0
				break
		if f:
			ans+=1
	else:
		ans+=1
print(ans)


Measured memory_bytes: 31764
status = []
for _ in range(3):
    row = list(map(int,input().split()))
    status.append(row)

sum_status = 0
sum_dig = 0
for h in range(3):
    for w in range(3):
        sum_status += status[h][w]
        if h == w:
            sum_dig += status[h][w]

if sum_dig*3 == sum_status:
    print("Yes")
else:
    print("No")

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

struct data {
  bool a, o;
  long long b;
};

long long r, c, q;
vector<data> query;

long long solve();

int main() {
  while(1) {
    cin >> r >> c >> q;
    if(r + c + q == 0) break;
    query.resize(q);
    for(int i = 0; i < q; ++i)
      cin >> query[q - 1 - i].a >> query[q - 1 - i].b >>
          query[q - 1 - i].o;
    cout << solve() << endl;
  }
  return 0;
}

long long solve() {
  long long ans = 0;
  set<long long> st[2];
  for(int i = 0; i < q; ++i) {
    data now = query[i];
    if(st[now.a].find(now.b) != st[now.a].end()) continue;
    if(now.o) {
      if(now.a)
        ans += r;
      else
        ans += c;
    }
    if(now.a)
      --c;
    else
      --r;
    st[now.a].insert(now.b);
  }
  return ans;
}


Measured memory_bytes: 6124
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)

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

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

    ll ans = 0;
    rep(i, 0, N-1){
        ll sum = a[i] + a[i+1];
        ll diff = sum - x;
        if(diff > 0){
            if(a[i+1] >= diff){
                a[i+1] -= diff;
                ans += diff;
            }else{
                a[i] -= (diff - a[i+1]);
                a[i+1] = 0;
                ans += diff;
            }
        }
    }
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define ll long long
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for(ll i = 0; i < n; i++)
const ll INF = 1LL << 60;


int main(){
    int N, M, A, B, C;
    string s1, s2;
    cin >> s1 >> s2;
    if(s1[0] > s2[0]) cout << '>' << endl;
    else if(s1[0] == s2[0]) cout << '=' << endl;
    else cout << "<" << endl;
}

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

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

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

int main()
{
  string ss;
  cin >> ss;
  if(ss[0] != 'A')
  {
    cout << "WA" << endl;
    return 0;
  }
  int64 cc = 0;
  for(int64 ii = 2;ii < ss.length() - 1;ii++)
  {
    if(ss[ii] == 'C')
    {
      cc++;
    }
  }
  if(cc != 1)
  {
    cout << "WA" << endl;
    return 0;
  }
  cc = 0;
  for(int64 ii = 0;ii < ss.length();ii++)
  {
    if(ss[ii] >= 'A' && ss[ii] <= 'Z')
    {
      cc++;
    }
  }
  if(cc != 2)
  {
    cout << "WA" << endl;
    return 0;
  }
  cout << "AC" << endl;
  return 0;
}


Measured memory_bytes: 3628
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <vector>
namespace fastIO{
#define getchar() my_getchar()
#define putchar(x) my_putchar(x)
#define debug(...) fprintf(stderr, __VA_ARGS__)
	static const int IN_BUF = 1 << 23, OUT_BUF = 1 << 23;
	char buf[IN_BUF], *ps = buf, *pt = buf;
	inline char my_getchar(){
		return ps == pt && (pt = (ps = buf) + fread(buf, 1, IN_BUF, stdin), ps == pt) ? EOF : *ps++;
	}
	template<typename T> inline bool read(T &x){
		char op = 0, ch = getchar();
		for (x = 0; !isdigit(ch) && ch != EOF; ch = getchar()) if (ch == '-') op ^= 1;
		if (ch == EOF) return false;
		for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ '0');
		if (ch != '.') return op ? x = -x : 0, true; else ch = getchar();
		T t = 1;
		for (; isdigit(ch); ch = getchar()) t /= 10, x += (ch ^ '0') * t;
		return op ? x = -x : 0, true;
	}
	inline int reads(char *s){
		int n = 0;
		char ch = getchar();
		for (; isspace(ch) && ch != EOF; ch = getchar()) ;
		for (; !isspace(ch) && ch != EOF; ch = getchar()) s[n++] = ch;
		return s[n] = '\0', n;
	}
	char pbuf[OUT_BUF], *pp = pbuf;
	struct _flusher{ ~_flusher(){ fwrite(pbuf, 1, pp - pbuf, stdout); } } OutputFlusher;
	inline void my_putchar(char x){
		pp == pbuf + OUT_BUF ? fwrite(pbuf, 1, OUT_BUF, stdout), pp = pbuf : 0, *pp++ = x;
	}
	template<typename T> inline void print_(T x){
		if (x == 0) return putchar('0'), void(0);
		std::vector<int> num;
		for (x < 0 ? putchar('-'), x = -x : 0; x; x /= 10) num.push_back(x % 10);
		while (!num.empty()) putchar(num.back() ^ '0'), num.pop_back();
	}
	template<typename T> inline void print(T x, char ch = '\n'){
		print_(x), putchar(ch);
	}
	inline void prints_(const char *s, int n = -1){
		if (n == -1) n = strlen(s);
		for (register int i = 0; i < n; ++i) putchar(s[i]);
	}
	inline void prints(const char *s, int n = -1, char ch = '\n'){
		prints_(s, n), putchar(ch);
	}
	template<typename T> inline void printd_(T x, int n){
		if (x < 0) x = -x, putchar('-');
		long long a, b;
		for (register int i = 0; i < n; ++i) x *= 10;
		x = (long long)(x + 0.5);
		for (register int i = 0; i < n; ++i) x /= 10;
		a = x, x -= a;
		for (register int i = 0; i < n; ++i) x *= 10;
		b = x;
		print_(a);
		if (n) putchar('.'); else return;
		std::vector<int> num(n);
		for (register int i = 0; i < n; ++i) num[i] = b % 10, b /= 10;
		while (!num.empty()) putchar(num.back() ^ '0'), num.pop_back();
	}
	template<typename T> inline void printd(T x, int n, char ch = '\n'){
		printd_(x, n), putchar(ch);
	}
}
using namespace fastIO;
const int N = 100005;
int n, m, k, p, a[N];
int main(){
#ifdef AT_HOME
	freopen("A.in", "r", stdin);
	freopen("A.out", "w", stdout);
#endif
	read(n), read(m), read(k), read(p);
	--k, k = std::max(0, k - (p - 1));
	for (register int i = 1; i <= n; ++i) read(a[i]);
	std::sort(a + 1, a + 1 + n);
	int ans = p - 1;
	long long sum = 0;
	for (register int i = 1; i <= n - p + 1; ++i) sum += a[i];
	for (register int i = 1; i <= n - p + 1; ++i){
		sum -= a[i];
		if (a[i] + m < a[n - p + 1]) continue;
		if (1ll * (i - 1) * m + 1ll * (n - p + 1 - i) * (a[i] + m) - sum >= 1ll * m * k) ++ans;
	}
	print(ans);
}


Measured memory_bytes: 2688
#define  _USE_MATH_DEFINES

#define  rep(i, n) for(int i = 0; i < n; i++)
#define  repx(i, a, n) for(int i = a; i < n; i++)
#define  loop while(1)
#define  lli long long int
 
#include <iostream>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <utility>
#include <set>
  
using namespace std;

void moveN(vector<int> &dice) {
  int tmp;
  tmp = dice[0];
  dice[0] = dice[1];
  dice[1] = dice[5];
  dice[5] = dice[4];
  dice[4] = tmp;
}

void moveS(vector<int> &dice) {
  int tmp;
  tmp = dice[0];
  dice[0] = dice[4];
  dice[4] = dice[5];
  dice[5] = dice[1];
  dice[1] = tmp;
}

void moveW(vector<int> &dice) {
  int tmp;
  tmp = dice[0];
  dice[0] = dice[2];
  dice[2] = dice[5];
  dice[5] = dice[3];
  dice[3] = tmp;
}

void moveE(vector<int> &dice) {
  int tmp;
  tmp = dice[0];
  dice[0] = dice[3];
  dice[3] = dice[5];
  dice[5] = dice[2];
  dice[2] = tmp;
}
 
int main() {

  vector<int> dice(6, 0);
  rep(i, 6) cin >> dice[i];

  string op;
  cin >> op;

  rep(i, op.size()) {
    if(op[i] == 'N') moveN(dice);
    if(op[i] == 'S') moveS(dice);
    if(op[i] == 'W') moveW(dice);
    if(op[i] == 'E') moveE(dice);
  }

  cout << dice[0] << endl;

  return 0;
}



Measured memory_bytes: 3180
use std::io::stdin;

fn main() {
    let mut s = String::new();
    stdin().read_line(&mut s).ok();
    let x: i128 = s.trim().parse().unwrap();

    'outer: for i in -10000i128..=10000 {
        //for j in -10000i128..=10000 {
        let mut l: i128 = -10000;
        let mut r: i128 = 10000;
        let mut m: i128;
        while l < r {
            m = (l + r) / 2;
            let t = i.pow(5) - m.pow(5);
            if t == x {
                println!("{} {}", i, m);

                break 'outer;
            } else if t < x {
                r = m - 1;
            } else {
                l = m;
            }
        }
    }
}


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

using namespace std;
vector<long long> factors;
#define ll long long

#define pii pair<int,int>
#define pll pair<ll,ll>
#define _ <<'\n'
#define __ << ' '
#define all(x) (x).begin(), (x).end()
#define gcd __gcd
int IT_MAX = 1 << 17;
int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
const double ERR = 1e-10;
#define szz(x) (int)(x).size()
#define IOS ios_base::sync_with_stdio(false); cout.tie(0);cin.tie(0);
#define flush fflush(stdout)

ll mod(ll a, ll m)
{ return (a + (abs(a) / m) * m + m) % m; }

//****************************don't use int!!!!!!!****************************//
//***************************code starts here!!!!!****************************//




int main()
{
	IOS

	ll n,m;
	cin >> n >>m;
	vector<pll> drs(n);
	for(int i = 0;i < n; ++i){
		cin >> drs[i].first >> drs[i].second;
	}
	sort(all(drs),[](pll a, pll b){
		return a.first < b.first;
	});
	ll total_cost = 0;
	ll ind = 0;
	while(m){
		ll temp = min<ll>(m,drs[ind].second);
		m-= temp;
		total_cost+=temp*drs[ind].first;
		++ind;
	}
	cout << total_cost;
	return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>

using namespace std;

int main() {
	char s;
	cin >> s;
	if (isupper(s)) {
		cout << "A" << endl;
	}
	else {
		cout << "a" << endl;
	}
	return 0;
}

Measured memory_bytes: 3064
using System;
using System.Collections.Generic;

namespace abc144_f
{
  class Program
  {
    static void Main(string[] args)
    {
      var n = CIn.ReadInt();
      var m = CIn.ReadInt();
      var p = new List<int>[n];

      for (var i = 0; i < n; i++)
      {
        p[i] = new List<int>();
      }

      for (var i = 0; i < m; i++)
      {
        var s = CIn.ReadInt() - 1;
        var t = CIn.ReadInt() - 1;

        p[s].Add(t);
      }

      var ans = (double)n - 1;

      for (var i = 0; i < n - 1; i++)
      {
        var dp = new double[n];

        if (p[i].Count == 1)
        {
          continue;
        }

        for (var j = n - 2; j >= 0; j--)
        {
          var pc = p[j].Count;
          var max = 0.0;

          for (var k = 0; k < pc; k++)
          {
            if (i == j)
            {
              var tmp = dp[p[j][k]] / (pc - 1);
              max = Math.Max(max, tmp);
              dp[j] += tmp;
            }
            else
            {
              dp[j] += dp[p[j][k]] / pc;
            }
          }

          dp[j] += 1 - max;
        }

        ans = Math.Min(ans, dp[0]);
      }

      Console.WriteLine(ans);
    }
  }

  class CIn
  {
    private static readonly Queue<string> fieldBuffer = new Queue<string>();

    public static string Read()
    {
      if (fieldBuffer.Count == 0)
      {
        foreach (var field in Console.ReadLine().Split())
        {
          fieldBuffer.Enqueue(field);
        }
      }
      return fieldBuffer.Dequeue();
    }

    public static int ReadInt() => int.Parse(Read());
    public static long ReadLong() => long.Parse(Read());
    public static double ReadDouble() => double.Parse(Read());

    public static string[] ReadStringArray(long n)
    {
      var array = new string[n];
      for (var i = 0; i < n; i++)
      {
        array[i] = Read();
      }
      return array;
    }

    public static int[] ReadIntArray(long n)
    {
      var array = new int[n];
      for (var i = 0; i < n; i++)
      {
        array[i] = ReadInt();
      }
      return array;
    }

    public static long[] ReadLongArray(long n)
    {
      var array = new long[n];
      for (var i = 0; i < n; i++)
      {
        array[i] = ReadLong();
      }
      return array;
    }

    public static double[] ReadDoubleArray(long n)
    {
      var array = new double[n];
      for (var i = 0; i < n; i++)
      {
        array[i] = ReadDouble();
      }
      return array;
    }
  }
}

Measured memory_bytes: 17708
#include<bits/stdc++.h>
using namespace std;
int main(){
  int W,H,X,Y;
  cin>>W>>H>>X>>Y;
  double ans=(double)W*H/2;
  int num;
  if(W==X*2&&H==Y*2){
    num=1;
  }
  else{
    num=0;
  }
  printf("%.10f %d\n",ans,num);
}


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

using namespace std;

const double Pi = 3.1415926535897932384626433832;
const double Exp = 2.718281828459045235360287471;

char x[1], y[1];

int main() {
	cin >> x[0] >> y[0];
	if(x[0] > y[0]) {
		puts(">");
	} else if (x[0] < y[0]) {
		puts("<");
	} else {
		puts("=");
	}
	return 0;
}


Measured memory_bytes: 256
"""
問題文は言い換えると、Aから隣同士の差がKを超えないよう用に部分列を抽出しろ、ということ。
Aの数値自体も30万以下という制約が気になる。
あと入力の与え方。Aが行くぎりで与えられている

方法１：
各数を使う使わないで場合分け→O(2^N)

方法２：
二分探索はいけるかな？
数列Bの長さをX以上にできるか？


×自分を使う場合、両隣は自分+-300000の範囲を許容できる。

方法３：
出現した数字をどこかにメモしておく

中央値をとる？

一つの数を取ると仮定して、

"""
class segTree:
    def __init__(self,n,identity):
        if bin(n).count("1") == 1:
            self.leaves = 2**(n.bit_length()-1)
        else:
            self.leaves = 2**n.bit_length()
        self.identity = identity
        self.tree = [self.identity]*(self.leaves*2)

    def merge(self,x,y):
        #ここにマージ処理を書く
        return max(x,y)

    def update(self,i,x):
        i = i+self.leaves
        self.tree[i] = x
        i >>= 1
        while i > 0:
            self.tree[i] = self.merge(self.tree[i*2],self.tree[i*2+1])
            i >>= 1

    def query(self,l,r):
        #[l:r)のクエリ結果を返す
        l = l + self.leaves
        r = r + self.leaves
        res = self.identity
        while l < r:
            if l&1:
                res = self.merge(res,self.tree[l])
                l += 1
            if r&1:
                r -= 1
                res = self.merge(res,self.tree[r])
            l >>= 1
            r >>= 1
        return res

N,K = map(int,input().split())
seg = segTree(300001,0)
for _ in range(N):
    a = int(input())
    bottom = max(a-K,0)
    upper = min(a+K,300000)
    tmp = seg.query(bottom,upper+1)
    seg.update(a,tmp+1)
print(seg.query(0,300001))




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

template<typename T, typename U> void dmax(T &x, U y) { if (x < y) x = y; }
template<typename T, typename U> void dmin(T &x, U y) { if (x > y) x = y; }

const int INF = 1001001001;

int main() {
  int x, n;
  int max_p = -INF, min_v;
  cin >> n >> min_v;
  while (cin >> x) {
    dmax(max_p, x - min_v);
    dmin(min_v, x);
  }

  cout << max_p << endl;
  return 0;
}

Measured memory_bytes: 3096
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] R = new int[n];
        for(int i = 0 ; i < n ; i++){
            R[i] = sc.nextInt();
        }
        
        int maxv = -2000000000;
        
        int minv = R[0];
        for(int i = 1 ; i < n ; i++){
            maxv = Math.max(maxv,R[i]-minv);
            minv = Math.min(minv,R[i]);
        }
        
        
        System.out.println(maxv);
    }
}


Measured memory_bytes: 100828
import sys

sys.setrecursionlimit(1000000)


def dfs(v):
    if cache[v] > -1:
        return cache[v]
    lv = links[v]
    cache[v] = ret = max(map(dfs, lv)) + 1 if lv else 0
    return ret


n, m = map(int, input().split())
links = [set() for _ in range(n)]
cache = [-1] * n
for line in sys.stdin.readlines():
    x, y = map(int, line.split())
    x -= 1
    y -= 1
    links[x].add(y)

print(max(map(dfs, range(n))))


Measured memory_bytes: 120752
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i < (n); i++)
using namespace std;
using ll=long long;
int main(){
  ll x;
  cin >>x;
  ll a, b;
  for(int a=0; a < (1000); a++){
    for(int b=-1000; b<a; b++){
      if ((pow(a,5.0)-pow(b,5.0))==x){
        cout << a << ' ' << b <<endl;
        return 0;
      }
    } 
  }
  return 0;
}

Measured memory_bytes: 4096
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define pb push_back
#define mp make_pair

using namespace std;

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

const int MOD = 1000000007;
const int INF = 2000000000;

vector<int> G[100000];
int V;
int color[100000];

bool dfs(int from, int c) {
    color[from] = c;
    for(int to : G[from]) {
        if(color[to] == c) return false;
        if(color[to] == 0 && !dfs(to, -c)) return false;
    }
    return true;
}

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

    rep(i, m) {
        int a, b;
        cin >> a >> b;
        G[a - 1].pb(b - 1);
        G[b - 1].pb(a - 1);
    }
    
    V = n;
    rep(i, V) {
        color[i] = 0;
    }

    int b = 0, w = 0;
    if(dfs(0, 1)) {
        rep(i, V) {
            if(color[i] == 1) b++;
            else w++;
        }
        cout << (ll)b * w - m << endl;
    }else cout << (ll)n * (n - 1) / 2 - m << endl;

    return 0;
}



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

int main(){
    int N;
    cin>>N;
    vector<ll> A(N);
    vector<ll> sum(N+1,0);
    for(int i=0; i<N; i++) cin>>A[i];
    for(int i=1; i<=N; i++){
        sum[i] = sum[i-1]+A[i-1];
    }

    ll ans = LLONG_MAX;

    for(int i=1; i<N; i++){
        ll left = sum[i];
        ll right = sum[N] - sum[i];
        ans = min(ans,abs(left-right));
    }

    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 3328
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <random>
#include <iomanip>
#include <bitset>
                        
using namespace std;
                        
template<typename T> void uin(T &a, T b) {
    if (b < a) {
        a = b;
    }
}

template<typename T> void uax(T &a, T b) {
    if (b > a) {
        a = b;
    }
}

#define int long long
#define ghost signed
#define left left228
#define right right228
#define prev prev228
#define list list228
#define complex complex228

int f(int n) {
	if (n == 0) return 1;
	return f(n - 1) * n;
}

ghost main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
	int n, a, b;
	cin >> n >> a >> b;
	if (a + b - 1 > n) {
		cout << -1 << '\n';
		return 0;
	}
	--a;
	vector<int> ans;
	vector< vector<int> > block(n + 1);
	int mxblock = 0;
	for (int i = 1; i <= n - b; ++i) {
		block[(i - 1) / a].push_back(i);
		mxblock = (i - 1) / a;
	}
	for (int i = mxblock; i >= 0; --i) {
		for (int x : block[i]) ans.push_back(x);
	}
	if (mxblock + 1 > b) {
		cout << -1 << '\n';
		return 0;
	}
	for (int i = n; i > n - b; --i) ans.push_back(i);
	for (int i : ans) cout << i << " ";
	cout << endl;
    return 0;
} // kek










/*3 3 2

3 3 2
3 3 2
2 3 3
2 3 3
*/








Measured memory_bytes: 18540
#define _USE_MATH_DEFINES
#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;

int main()
{
    double a,b,c,C,S,L,h;
    cin >> a >> b >> C;
    h = b * sin(C*M_PI/180);
    S = a * h / 2;
    c = a - b * cos(C*M_PI / 180);
    c = pow(h * h + c * c, 1. / 2);
    L  = a + b + c;
    cout << fixed << setprecision(5)
         << S << endl
         << L << endl
         << h << endl;
    return 0;
}



Measured memory_bytes: 3580
#include<iostream>
#include<vector>
#include<map>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#include<stack>
#include<queue>
#include<set>
#include<bitset>
#include<iomanip>
#define BUG puts("no bug")
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define ll long long
#define ull unsigned long long
#define REP(a,b,c) for(ll a=b;a<=c;a++)
#define PER(a,b,c) for(ll a=b;a>=c;a--)
#define lb(a) (a&(-a))
#define pp (p<<1)
#define ppp (p<<1|1)
#define pi pair<ll,ll>
#define pii pair<pair<ll,ll>,ll>
using namespace std;
const ll MAXN=1e6+5;
ll n,m,t;
ll ans;
ll v[MAXN];
ll dp[MAXN];
ll mod=998244353;
int main(){
    cin>>n>>m;
    REP(i,1,n)cin>>v[i];
    REP(i,1,n){
        PER(j,m,v[i])dp[j]=(dp[j]+dp[j-v[i]])%mod;
        dp[v[i]]=(dp[v[i]]+i)%mod;
        ans=(ans+(dp[m])*(n-i+1)%mod)%mod;
        dp[m]=0;
    }
    cout<<ans;
}

Measured memory_bytes: 2304