akhauriyash/Code-Regression huggingface dataset:
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {
    private static java.util.Scanner scanner = new java.util.Scanner(System.in);

    public static void main(String[] args) {
        int n = scanner.nextInt(), ans[] = new int[n];
        List<Integer> b = IntStream.range(0, n)
                .mapToObj(i -> scanner.nextInt())
                .collect(Collectors.toList());
        while (n > 0)
            for (int i = n, d = 0; i > 0 && n > d; i--)
                switch (Integer.compare(b.get(i - 1), i)) {
                    case 1:
                        System.out.println(-1);
                        return;
                    case 0:
                        ans[--n] = b.get(i - 1);
                        b.remove(i - 1);
                        continue;
                    case -1:
                        d = Math.max(d, n - i + b.get(i - 1));
                }
        for (int i : ans)
            System.out.println(i);
    }
}

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

int main(){
    int H, W;
    while(1){
        cin >> H >> W;
        if(H == 0 && W == 0) break;
        for(int i = 0; i < H; i++){
            for(int j = 0; j < W; j++){
                cout << "#";
            }
            cout << endl;
        }
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 3112
#include <bits/stdc++.h>
using namespace std;
int main(){
int h,w;
  cin >> h >> w;
  char a[h][w];
  for (int i=0;i<h;i++){
    for (int j=0;j<w;j++){
      cin >> a[i][j];
    }
  }
  bool ans=true;
  for (int i=0;i<h-1;i++){
    for (int j=0;j<w-1;j++){
      if (a[i+1][j]=='#' && a[i][j+1]=='#')ans=false;
    }
  }
  if (ans)cout << "Possible" <<endl;
    else cout << "Impossible" << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <utility>
#include <tuple>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cmath>
#define rep(i, n) for(int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, T b) {
 if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int main(){
  int N;
  cin >> N;
  vector<int> v(N);
  rep(i, N) cin >> v[i];
  sort(v.begin(), v.end());
  double made = (v[0]+v[1])/2.0;
  for(int i=2; i<N; i++)
    made = (made+v[i])/2;
  cout << made << endl;
  return 0;
}

Measured memory_bytes: 256
n=int(input())
s=str(input())
t=str(input())
listed=[]
cnt=0
while cnt<=n-1:
    if s[cnt]==t[cnt]:
        cnt+=1
        listed.append("T")
    elif s[cnt]==s[cnt+1] and t[cnt]==t[cnt+1]:
        cnt+=2
        listed.append("Y")

length=len(listed)
if listed[0]=="T":
    ans=3
elif listed[0]=="Y":
    ans=6
for i in range(0,length-1):
    
    if listed[i]=="Y" and listed[i+1]=="Y":
        ans=ans*3%(10**9+7)
    
    if listed[i]=="Y" and listed[i+1]=="T":
        ans=ans
        
    if listed[i]=="T" and listed[i+1]=="Y":
        ans=ans*2%(10**9+7)
        
        
    if listed[i]=="T" and listed[i+1]=="T":
        ans=ans*2%(10**9+7)
print(ans)

Measured memory_bytes: 3064
import java.util.*;
public class Main{
  public static void main (String args[]){
    Scanner sc = new Scanner(System.in);
    
    int n = sc.nextInt();
    
    int l = sc.nextInt();
    
    List<String> list = new ArrayList<>();
    
    for (int i = 0; i < n; i++){
      list.add(sc.next());
    }
    
    Collections.sort(list);
    
    for (int i = 0; i < n; i++){
      System.out.print(list.get(i));
    }
    
  }
}

Measured memory_bytes: 22100
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;


int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);

    string s;
    cin >> s;
    int n = s.length();

    const int INF = 1 << 24;
    vector<int> dp(2, INF);
    dp[0] = 0;
    dp[1] = 0;
    vector<int> ndp(dp);

    for (int i = 0; i < n; ++i) {
        fill(ndp.begin(), ndp.end(), INF);
        int d = s[i] - '0';
        for (int j = 0; j < 2; ++j) {
            if (dp[j] >= INF) {
                continue;
            }
            for (int k = 0; k < 2; ++k) {
                int ct = 0;
                if ((k ^ j) == 0) {
                    continue;
                }
                if (k != d) {
                    ++ct;
                }
                ndp[k] = min(ndp[k], dp[j] + ct);
            }
        }
        swap(ndp, dp);
    }

    cout << min(dp[0], dp[1]) << '\n';
    return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

using namespace std;
using namespace __gnu_pbds;

//find_by_order gives kth-largest element
//order_of_key gives the number of items in the set that are strictly smaller!!

// OT.find_by_order(k-1)
// 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

#define db(x) cerr << #x << "=" << x << endl
#define db2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define db3(x, y, z) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define db4(x, y, z, w) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << "," << #w << "=" << w << endl
#define ll long long
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define X first
#define Y second
#define sz(x) (int)((x).size())
#define pii pair<int,int>
#define MOD (ll)(1e9 + 7)
#define rep(i, n)    for(int i = 0; i < (n); ++i)
#define repA(i, a, n)  for(int i = a; i <= (n); ++i)
#define repD(i, a, n)  for(int i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
typedef vector<int> vi;
#define inf (ll)(1e18)
#define double long double
#define int long long

//////////////////////

int32_t main() {

    ios::sync_with_stdio(false);
    cin.tie(0); 
    cout.tie(0);

    int a;
    cin >> a;
    string s;
    cin >> s;

    if(a >= 3200)
        cout << s << '\n';
    else
        cout << "red" << '\n';
}

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

using namespace std;

#define all(v)				((v).begin()), ((v).end())
#define allr(v)				((v).rbegin()), ((v).rend())
#define sz(v)				((int)((v).size()))
#define rep(i, v)		for(int i=0;i<sz(v);++i)
#define lp(i, n)		for(int i=0;i<(int)(n);++i)
#define lpi(i, j, n)	for(int i=(j);i<(int)(n);++i)
#define lpd(i, j, n)	for(int i=(j);i>=(int)(n);--i)
#define ll long long
#define pb					push_back
#define fIO ios_base::sync_with_stdio(0);cin.tie(0);

const ll oo = 1e7;
const double pi = 3.1415926535897;


const double EPS = (1e-7);
int dcmp(double x, double y) {	return fabs(x-y) <= EPS ? 0 : x < y ? -1 : 1;	}


typedef vector<int>                vi;
typedef vector<pair<int,int>>      vii;
typedef vector<ll>                 vll;
typedef vector<double>             vd;
typedef vector< vi >               vvi;
typedef vector< vd >               vvd;
typedef vector<string>             vs;

/**
    * PLEASEEE READDD PROBLEEEM CARFULLY ****
    * Always check for OVERFLOW ll vs int
    * Always check for array bounds
    * Check for function return
    * READ OUTPUT SECTION AGAIN!!!
**/

struct edge{
    int from,to,w;
    edge(int uu,int vv,int ww):from(uu),to(vv),w(ww){}

    bool operator < (const edge &rhs) const{
        return w > rhs.w;
    }
};

const int N = 205;

int main(){
   /* string s1,s2;
    cin >> s1 >> s2;
    int ans = 0;
    for(int i = 0;i<s1.length();i++){
        ans += s1[i] == s2[i];
    }
    cout <<ans;*/
    /*int a,b;
    cin >> a >> b;
    if(b == 1)
        return cout << 0,0;
    int ans = 1,sockets = a;
    while(sockets < b){
        ans++;
        sockets += a-1;
    }
    cout << ans;
    */
    /*
    int n;
    cin >>n;
    int arr[n];
    lp(i,n)cin >> arr[i];
    int maxi = 0;
    int idx = 1;
    while(idx<n){
        int ans = 0;
        int f  = 1;
        while(idx < n && arr[idx] <= arr[idx-1]){
                ans++;idx++;
                f = 0;
        }
        if(f)idx++;
        //cout << idx<<endl;
        maxi = max(ans,maxi);
    }
    cout << maxi;
    */
    ll n;
    cin >> n;
    ll ans = n*(n-1);
    cout << ans/2;
}












Measured memory_bytes: 764
#include <stdio.h>
int j,N;
int A[100];
int key;

void print(){
  int i;
  for(i=0;i<N;i++){
    printf("%d",A[i]);
    if(i<N-1)printf(" ");
  }
  printf("\n");
}

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

  for(i=1;i<N;i++){
    key = A[i];
    j = i -1;
    
    while (j >= 0 && A[j] > key){
      A[j+1] = A[j];
      j--;

    }

    A[j+1] = key;
    print();
  }

    return 0;
}

Measured memory_bytes: 604
import java.util.Scanner;
 
public class Main {
 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
		long X = scan.nextLong();
		long Y = scan.nextLong();
		int length = 0;
		while(X <=Y){
			length++;
			X *=2;
		}
		System.out.println(length);
	}
	
//	public static boolean func(long num,long A,long B){
//		long temp = 0;
//		do {
//			temp += num % 10;
//			num/=10;
//		} while (num != 0);
//		
//		if(temp < A || temp > B){
//			return true;
//		}else{
//			return false;
//			
//		}
//		
//		
//	}
 
}

Measured memory_bytes: 25172
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i) = 0; (i) < (n); ++(i))
#define rrep(i,n) for(int (i) = (n) - 1; (i) >= 0; --(i)) //Reversi rep
#define nfor(i,a,b) for(int (i) = (a); (i) < (b); ++(i)) //Natural for
#define rfor(i,a,b) for(int (i) = (b); (i) >= (a); --(i)) //Reversi for

int main()
{
    int a,b,c;
    cin >> a >> b >> c;
    if(a+b == c){
        cout << "Yes" << endl;
    }else if(a+c == b){
        cout << "Yes" << endl;
    }else if(b+c == a){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
 
int main(void)
{
    int a, b;
    scanf("%d %d", &a, &b);
 
    if (a < b)
        puts("a < b");
    else if (a > b)
        puts("a > b");
    else
        puts("a == b");
 
    return (0);
}

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

int main(void)
{
    ll k, a, b;
    cin >> k >> a >> b;
    ll ans = 1;
    rep(i, k)
    {
        if (ans < a || k - i < 2 || a + 1 >= b)
            ans++;
        else
            ans -= a, i++, ans += b;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3568
import math

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

X=int(input())

while True:
    if is_prime(X):break
    X+=1
    
print(X)

Measured memory_bytes: 9044
n = int(input())
s = input()

r_num = s.count("R")
g_num = s.count("G")
b_num = s.count("B")

ans = r_num * b_num * g_num

for i in range(n):
    for j in range(i+1, n):
        k = 2 * j - i
        if k >= n:
            break

        if (s[i] != s[j] and 
            s[j] != s[k] and
            s[i] != s[k]):
            ans += -1
 
print(ans)

Measured memory_bytes: 9096
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define pb push_back
using namespace std;
using ll = long long;
const int maxn = 1<<18;
signed main() {
	cin.tie(0)->sync_with_stdio(0);
int n, a, b;
cin >> n >> a >> b;
while(a <= b) if(a%n == 0) return cout << "OK", 0; else a++;
cout << "NG";	
return 0;
}


Measured memory_bytes: 3544
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const long long maxn=100000+50;
long long n,m,w[maxn],v[maxn],dp[maxn];
int main()
{
	cin>>n>>m;
	for(long long i=1;i<=n;i++)cin>>w[i]>>v[i];
	memset(dp,0x7f7f7f7f,sizeof(dp));
	dp[0]=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=100000;j>=v[i];j--)
		{
			if(dp[j-v[i]]||j-v[i]==0)
			{
				dp[j]=min(dp[j],dp[j-v[i]]+w[i]);
			}
		}
	}
	for(int j=100000;j>=1;j--)
	{
		if(dp[j]&&dp[j]<=m)
		{
			cout<<j<<endl;
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 4392
//#include <bits/stdc++.h>
//#include <stdio.h>
#include<iostream>
#include<cstdio>
#include<bitset>
#include<algorithm>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<string.h>
#include<cmath>
#include<utility>
#include<functional>
#include<map>
#include<set>
#include<cctype>
#include<fstream>
#include <numeric>
 
#define FOR(i, a, b) for( int i=(a);i<=(b);i++)
#define RFOR(i, a, b) for( int i=(a);i>=(b);i--)
#define LFOR(i, a, b) for( long long int i=(a);i<=(b);i++)
#define LRFOR(i, a, b) for(long long int i=(a);i>=(b);i--)
#define MOD 1000000007
using namespace std;
using ll=long long;
constexpr ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
constexpr ll lcm(ll a,ll b){return a*b/gcd(a,b);}

int main() {
  int N, K;
  cin >> N >> K;
  int ans=1;
  
  if(N%K==0){
    ans=0;
  }

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

Measured memory_bytes: 256
#include <iostream>

using namespace std;

unsigned long long int power_aux(unsigned long long int base, unsigned long long int exponent, unsigned long long int accumulator) {
  if (exponent == 0) {
    return accumulator % 1000000007;
  } else if (base >= 1000000007 || accumulator >= 1000000007) {
    return power_aux(base % 1000000007, exponent, accumulator % 1000000007);
  } else if (exponent % 2 == 0) {
    return power_aux(base * base, exponent/2, accumulator);
  } else {
    return power_aux(base, exponent - 1, accumulator * base);
  }
}

unsigned long long int power(unsigned long long int base, unsigned long long int exponent) {
  return power_aux(base, exponent, 1);
}

int main() {
  unsigned long long int base, exponent;
  cin >> base >> exponent;
  cout << power(base, exponent) << endl;
}
  

Measured memory_bytes: 1156
import java.util.Scanner;

public 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 d;
		if(a>c){
			d = a;
			a = c;
			c = d;
		}
		if(b>c){
			d = b;
			b = c;
			c = d;
		}
		if(a>b){
			d = a;
			a = b;
			b = d;
		}
		System.out.println(a + " " + b + " " + c);
	}
}


Measured memory_bytes: 26316
import sys
sys.setrecursionlimit(10**7)
def main(n,ki,uv):
  # n: 頂点数
  # ki: 木
  # Euler Tour の構築
  S=[] # Euler Tour
  F=[0]*n # F[v]:vにはじめて訪れるステップ
  depth=[0]*n # 0を根としたときの深さ
  def dfs(v,pare,d):
      F[v]=len(S)
      depth[v]=d
      S.append(v)
      for i,w in ki[v]:
          if w==pare:continue
          dfs(w,v,d+1)
          S.append(v)
  dfs(0,-1,0)
  # Sをセグメント木に乗せる
  # u,vのLCAを求める:S[F[u]:F[v]+1]のなかでdepthが最小の頂点を探せば良い
  # F[u]:uに初めてたどるつくステップ
  # S[F[u]:F[v]+1]:はじめてuにたどり着いてつぎにvにたどるつくまでに訪れる頂点
  # 存在しない範囲は深さが他よりも大きくなるようにする
  INF = (n, None)
  # LCAを計算するクエリの前計算
  M = 2*n
  M0 = 2**(M-1).bit_length() # M以上で最小の2のべき乗
  data = [INF]*(2*M0)
  for i, v in enumerate(S):
    data[M0-1+i] = (depth[v], i)
  for i in range(M0-2, -1, -1):
    data[i] = min(data[2*i+1], data[2*i+2])
  # LCAの計算 (generatorで最小値を求める)
  def _query(a, b):
    yield INF
    a += M0; b += M0
    while a < b:
      if b & 1:
        b -= 1
        yield data[b-1]
      if a & 1:
        yield data[a-1]
        a += 1
      a >>= 1; b >>= 1
  # LCAの計算 (外から呼び出す関数)
  def query(u, v):
    fu = F[u]; fv = F[v]
    if fu > fv:
      fu, fv = fv, fu
    return S[min(_query(fu, fv+1))[1]]
  

  todo=[[0,[]]]
  path=[[]]*n
  mi=[1]*n
  while todo:
    v,ary=todo.pop()
    path[v]=ary
    mi[v]=0
    for i,nv in ki[v]:
      if mi[nv]==1:
        todo.append([nv,ary+[i]])
        mi[nv]=1

  for i in range(n):
    path[i]=set(path[i])
  memo={}
  ans=0
  for i in range(2**m):
    chk=set(())
    for j in range(m):
      if (i>>j)&1:
        chk.add(j)
    must_w=set(())
    for c in chk:
      if c in memo:
        tmp=memo[c]
      else:
        u,v=uv[c]
        dd=query(u,v)
        tmp=path[u]|path[v]
        tmp-=path[dd]
        memo[c]=tmp
      must_w|=tmp
    t=n-1-len(must_w)
    if len(chk)%2==1:
      ans-=pow(2,t)
    else:
      ans+=pow(2,t)
  print(ans)
if __name__=='__main__':
  n=int(input())
  ki=[[] for _ in range(n)]
  for i in range(n-1):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    ki[u].append([i,v])
    ki[v].append([i,u])
  m=int(input())
  uv=[]
  for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    uv.append([u,v])
  main(n,ki,uv)


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

using namespace std;
int main() {
  int n;
  cin >> n;
  if (n % 2 == 1) {
    cout << "No" << endl;
    return 0;
  }
  string s;
  cin >> s;

  int half = n / 2;
  if (s.substr(0, half) == s.substr(half)) {
    cout << "Yes" << endl;
    return 0;
  }
  cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, start, end) for (long long i = start; i < end; ++i)
#define repreverse(i, start, end) for (long long i = start; i >= end; --i)
#define all(x) (x).begin(), (x).end()
#define len(x) ((long long)(x).size())
#define lcm(a, b) ((a) / __gcd((a), (b)) * (b))
using namespace std;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vllvll = vector<vll>;
using pll = pair<ll, ll>;
template<class T>void print1d(T x,ll n=-1){if(n==-1)n=x.size();rep(i,0,n){cout<<x[i]<<' ';}cout<<'\n';}
template<class T>void print2d(T x,ll r=-1,ll c=-1){if(r==-1)r=x.size();if(c==-1)c=x[0].size();rep(i,0,r)print1d(x[i],c);}
template<class T, class U>bool haskey(T mp, U key) { return mp.find(key) != mp.end(); }
template<class T, class U>bool isin(T el, U container) { return find(all(container), el) != container.end(); }
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
template<class T>bool even(T n) { return ! (n & 1); }
template<class T>bool odd(T n) { return n & 1; }
template<class T>ld deg2rad(T deg) { return M_PI * deg / 180.0; }
template<class T>ld rad2deg(T rad) { return 180.0 * rad / M_PI; }
ll intpow(ll a,ll n){ll p=1;while(n){if(n&1)p*=a;a*=a;n>>=1;}return p;}
const long double pi = M_PI;
const long long big = 1LL << 50;
const long long inf = 1LL << 60;
const long long mod = 1e9 + 7;



int main()
{
        string S;
        cin >> S;
        map<char, ll> mp;
        rep(i, 0, len(S)) mp[S[i]]++;

        for (char alph = 'a'; alph <= 'z'; ++alph) {
                if (mp[alph] == 0) {
                        cout << alph << endl;
                        return 0;
                }
        }
        cout << "None" << endl;
}

Measured memory_bytes: 3704
N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

ret = 1
MOD = 10 ** 9 + 7

from collections import Counter
import sys

ca = Counter(A)
cb = Counter(B)

if ca.most_common(1)[0][1] >= 2 or cb.most_common(1)[0][1] >= 2:
    print(0)
    sys.exit(0)

A.sort()
B.sort()

import bisect


def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect.bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1


for n in range(N * M, 0, -1):
    a = index(A, n)
    b = index(B, n)
    cntA = len(A) - bisect.bisect_right(A, n)
    cntB = len(B) - bisect.bisect_right(B, n)

    # 両方みつけた
    if a != -1 and b != -1:
        pass

    # Bの方だけ見つけた
    elif a == -1 and b != -1:
        ret *= cntA

    # Aの方だけ見つけた
    elif a != -1 and b == -1:
        ret *= cntB

    # 両方なかった
    else:
        ret *= (cntA * cntB - (N * M - n))
    ret = ret % MOD

print(ret)


Measured memory_bytes: 48084
#EDP-E
import sys
n,W = map(int, sys.stdin.readline().split())

dp = [[1000000001 for i in range(100001)] for _ in range(n)]


w, v = map(int, sys.stdin.readline().split())
dp[0][v] = w

for i in range(1, n):
    w, v = map(int, sys.stdin.readline().split())
    for va in range(100001): #全ての価値を全探索
        if va < v: #上の結果を下に移す
            dp[i][va] = dp[i-1][va]
        else: #va >= v　の場合は va = v + (va-v)
            dp[i][va] = min(dp[i-1][va], dp[i-1][va-v] + w)
    dp[i][v] = min(dp[i][v], w)

ans =0
for v in range(100000,-1,-1): #価値の大きいほうから調べる
    #print(dp[-1][v])
    if dp[-1][v] <=W:
        #print(dp[-1][v], v)
        ans = v
        break
print(ans)

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

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

using ll=long long;
using R=long double;
const R EPS=1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max(x,0.0L));}

const int dx[8]={1,0,-1,0,1,-1,-1,1};
const int dy[8]={0,1,0,-1,1,1,-1,-1};

// Problem Specific Parameter:

vector<string> ary;

int main(void){
	string s;
	cin >> s;

	int k;
	cin >> k,k--;

	const int n = s.size();
	rep(i,n)rep(j,1,6) ary.push_back(s.substr(i,j));

	sort(begin(ary),end(ary));
	ary.erase(unique(begin(ary),end(ary)),end(ary));

	cout << ary[k] << endl;

	return 0;
}

Measured memory_bytes: 1660
#include <bits/stdc++.h>
using namespace std;
int main(){
  int a,b,c;
  cin >> a >> b >> c;
  vector<int> vec = {a,b,c};
  sort(vec.begin(),vec.end());
  int sum = vec[0]+vec[1];
  if(sum == vec[2]){
    cout << "Yes";
  }
  else{
    cout << "No";
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL_DEBUG
  #include "LOCAL_DEBUG.hpp"
#endif
#define int long long

void fail(){
  cout << "Impossible" << endl;
  exit(0);
}

signed main(){

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

  int Max = *max_element(a.begin(),a.end());
  vector<bool> used(n, false);
  sort(a.begin(),a.end());
  if(Max % 2 == 0){
    for(int i = Max/2+1; i <= Max; i++){
      int pos = lower_bound(a.begin(),a.end(),i) - a.begin();
      if(pos == n-1 || a[pos] != i || a[pos+1] != i) fail();
      used[pos] = used[pos+1] = true;
    }
    int pos = lower_bound(a.begin(),a.end(),Max/2) - a.begin();
    if(a[pos] != Max/2) fail();
    used[pos] = true;
    for(int i = 0; i < n; i++){
      if(!used[i] && !(Max/2 + 1 <= a[i] && a[i] <= Max)) fail();
    }
  }else {
    for(int i = (Max+1)/2; i <= Max; i++){
      int pos = lower_bound(a.begin(),a.end(),i) - a.begin();
      if(pos == n-1 || a[pos] != i || a[pos+1] != i) fail();
      used[pos] = used[pos+1] = true;
    }
    for(int i = 0; i < n; i++){
      if(!used[i] && !((Max+1)/2 + 1 <= a[i] && a[i] <= Max)) fail();
    }
  }
  cout << "Possible" << endl;

  return 0;
}


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

int main() {
  int64_t n,ans=0;
  cin >>n;
  
  map<string,int> m;
  for(int i=0;i<n;i++){
    string s;
    cin >> s;
    sort(s.begin(),s.end());
    if(m.count(s)){
      ans += m[s];
    }
    m[s]++;
  }
  
  cout << ans << endl;
  
  return 0;
}

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

#define F first
#define S second
#define ll long long
#define ld long double
#define pb push_back
#define INF 1e9

int taro(vector <int>& A,int k,int mn,vector <int>& dp){
	
	int n = A.size();
	if(k<mn){ dp[k]=0; return 0;}
	if(dp[k]>=0) return dp[k];
	for(int i=0;i<n;i++){
		if(k>=A[i]){if(!taro(A,k-A[i],mn,dp)){ dp[k]=1; return 1;} }
		}
		dp[k]=0; return 0;
	}

int main(){
	int n,k;
	cin>>n>>k;
	vector <int> A (n);
	int mn = INF;
	for(int i=0;i<n;i++){ cin>>A[i]; mn=min(mn,A[i]); }
	vector <int> dp (k+1,-1);
	if(taro(A,k,mn,dp)) cout<<"First"<<"\n";
	else cout<<"Second"<<"\n";
	return 0;
}


Measured memory_bytes: 8448
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.root = [-1] * (n + 1)
		self.rank = [0] * (n + 1)

	def find(self, x):
		if self.root[x] < 0:
			return x
		else:
			self.root[x] = self.find(self.root[x])
			return self.root[x]

	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return 0
		elif self.rank[x] > self.rank[y]:
			self.root[x] += self.root[y]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			self.root[x] = y
			if self.rank[x] == self.rank[y]:
				self.rank[y] += 1

	def isSame(self, x, y):
		return self.find(x) == self.find(y)

	def size(self, x):
		return -self.root[self.find(x)]


import sys
input = sys.stdin.buffer.readline

n, m, k = map(int, input().split())
friend = UnionFind(n)
f_cnt = [0] * n
for _ in range(m):
	a, b = map(int, input().split())
	a -= 1
	b -= 1
	friend.unite(a, b)
	f_cnt[a] += 1
	f_cnt[b] += 1
block = [[] for _ in range(n)]
for _ in range(k):
	c, d = map(int, input().split())
	block[c - 1].append(d - 1)
	block[d - 1].append(c - 1)
ans = []
for i in range(n):
	ret = friend.size(i) - f_cnt[i] - 1
	for j in block[i]:
		if friend.isSame(i, j):
			ret -= 1
	ans.append(ret)
print(*ans)


Measured memory_bytes: 29416
#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int n,k,x,y;
	scanf("%d%d%d%d",&n,&k,&x,&y);
	int ans;
	ans = n>k?k*x+(n-k)*y:n*x;
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdint>
#include <map>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <cstddef>
#include <cctype>
#include <iomanip>
#include <iostream>
#include <tuple>
#include <utility>
#include <math.h>
#include <stack>

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

/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
*/

const long long mod = 1e9+7;

void chmod(long long &M){
    if(M >= mod) M %= mod;
    else if(M < 0){
        M += (abs(M)/mod + 1)*mod;
        M %= mod;
    }
}

long long modpow(long long x, long long n){
    if(n==0) return 1;
    long long res=modpow(x, n/2);

    if(n%2==0) return res*res%mod;
    else return res*res%mod*x%mod;
}

int getl(int i, int N) { return i==0? N-1:i-1; };
int getr(int i, int N) { return i==N-1? 0:i+1; };



/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */

bool bin_search(std::vector<int> &a, int key) {
    int n = a.size();
    int left = 0;
    int right = n+1;
    while(right-left > 1) {
        int mid = (left+right) / 2;
        if(a[mid] <= key) { left = mid; }
        else { right = mid; }
    }
    
    if(a[left] == key) { return true; }
    else { return false; }
}

int main() {
    int n;
    scanf("%d", &n);
    std::vector<int> a(n+2);
    a[0] = -1;
    a[n+1] = 1e9+1;
    for(int i=1; i<=n; ++i) { scanf("%d", &a[i]); }
    
    int m;
    scanf("%d", &m);
    std::vector<int> b(m);
    for(int i=0; i<m; ++i) { scanf("%d", &b[i]); }

    int ans = 0;
    for(int i=0; i<m; ++i) if(bin_search(a, b[i])) { ++ans; }
    printf("%d\n", ans);

    return 0;
}



Measured memory_bytes: 3408
#include <iostream>
#include <algorithm>
#include <array>

using namespace std;

int main() {
    ios::sync_with_stdio(false);

    int N; cin >> N;
    array<int, 3> dp{};
    for (int i = 0; i < N; ++i) {
        array<int, 3> today;
        for (int j = 0; j < 3; ++j)
            cin >> today[j];

        array<int, 3> next{};
        for (int j = 0; j < 3; ++j)
            for (int k = 0; k < 3; ++k)
                if (j != k)
                    next[k] = max(next[k], dp[j] + today[k]);
        dp = next;
    }

    cout << *max_element(dp.begin(), dp.end()) << "\n";
}


Measured memory_bytes: 384
a = gets.to_i
b = gets.to_i
c = gets.to_i
x = gets.to_i

count = 0

(0..a).each do |d|
  (0..b).each do |e|
    (0..c).each do |f|
      if x == (500 * d) + (100 * e) + (50 * f)
        count += 1
      end
    end
  end
end

puts count

Measured memory_bytes: 1788
main = do
 [sx,sy,tx,ty]<-map read. words <$> getLine
 let dx = tx-sx
 let dy = ty-sy
 let l1 = "L"++ (replicate (dy + 1) 'U') ++ (replicate (dx + 1) 'R') ++ "D"
 let l2 = (replicate dx 'L') ++ (replicate dy 'D')
 let l3 = (replicate dx 'R') ++ (replicate dy 'U')
 let l4 = "R" ++ (replicate (dy + 1 ) 'D') ++ (replicate (dx + 1) 'L') ++ "U"
 putStrLn (l1 ++ l2 ++ l3 ++ l4)
 


Measured memory_bytes: 1020
#include <stdio.h>
int main(void)
{
	int n;
	double siz[40];
	int i, j;
	int grade[6] = {0, 0, 0, 0, 0, 0};
	
	scanf("%d", &n);
	
	for (i = 0; i < n; i++){
		scanf("%lf", &siz[i]);
		if(siz[i] >= 185.0){
			grade[5]++;
		}
		else if(siz[i] >= 180.0){
			grade[4]++;
		}
		else if(siz[i] >= 175.0){
			grade[3]++;
		}
		else if(siz[i] >= 170.0){
			grade[2]++;
		}
		else if(siz[i] >= 165.0){
			grade[1]++;
		}
		else {
			grade[0]++;
		}
	}
	
	for (i = 0; i < 6; i++){
		printf("%d:", i+1);
		
		for(j = 1; j <= grade[i]; j++){
			printf("*");
		}
		puts("");
	}
	
	return (0);
}

Measured memory_bytes: 648
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    List<Integer> weights = new ArrayList<>();
    for (int i = 0; i < N; i++) {
      Integer weight = sc.nextInt();
      weights.add(weight);
    }
    int result = N*100;
    for (int i = 0; i < N; i++) {
      int a = weights.subList(0,i).stream().mapToInt(Integer::intValue).sum();
      int b = weights.subList(i,weights.size()).stream().mapToInt(Integer::intValue).sum();
      int temp = Math.abs(a - b);
      if (temp < result) {
        result = temp;
      }
    }
    System.out.println(result);
  }
}

Measured memory_bytes: 29012
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cmath>
#include <climits>
#include <ctime>
#define endl '\n'
#define ll long long
#define mod 1000000007
#define NCONS 200001
//#define NCONS 100001
#define MCONS 1001
#define LIMIT 1000000000

using namespace std;

int main(void)
{
    cin.tie(NULL); ios_base::sync_with_stdio(false);
    vector<int> vec(5, 0); for(int i = 0; i < 5; i++) cin >> vec[i];
    int ret = 0;
    
    for(int i = 0; i < vec.size(); i++)
    {
        ret += vec[i];
      //  cout << ret << endl;
    }
    int m = INT_MAX;
    int idx = -1;
    
    for(int i = 0; i < vec.size(); i++)
    {
        if(vec[i] % 10)
        {
            if(vec[i] % 10 < m)
            {
                m = vec[i] % 10;
                idx = i;
            }
        }
    }
    
    for(int i = 0; i < vec.size(); i++)
    {
        if(idx == i) continue;
        if(vec[i] % 10 == 0) continue;
        ret += 10 - (vec[i] % 10);
    }
    
    cout << ret << endl;
    
    return 0;
}


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

#if debug
#include "printer.hpp"
#define dump(a) cerr << #a << "(" << __LINE__ << ") = " << a << endl;
#else
#define dump(...)
#endif

#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define repr(i, a, b) for (int i = (b)-1; i >= a; i--)
#define all(x) (x).begin(), (x).end()

using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pii;
const ll mod = 1000000007;

ll pow(ll x, ll y) {
  ll ret = 1, tmp = x;
  while (y) {
    if (y % 2) ret = ret * tmp % mod;
    tmp = tmp * tmp % mod;
    y /= 2;
  }
  return ret;
}

ll inverse(ll x) { return pow(x, mod - 2); }

int main() {
  ll N, M;
  cin >> N >> M;
  vi ac(N);
  ll cnt1 = 0;
  vi cnt2(N);
  rep(i, 0, M) {
    ll p;
    string s;
    cin >> p >> s;
    p--;
    if (s == "AC") {
      if (ac[p] == 0) {
        ac[p]=1;
        cnt1++;
      }
    } else {
      if (ac[p] == 0) {
        cnt2[p]++;
      }
    }
  }
  ll cnt3 = 0;
  rep(i, 0, N) {
    if (ac[i])  cnt3 += cnt2[i];
  }
  cout << cnt1 << ' ' << cnt3 << endl;
}


Measured memory_bytes: 1920
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#define rep(i, a, b) for(int i = a; i < (b); ++i)
using namespace std;
int main() {
    string S;
    cin >> S;
    long long res = 0;
    int cnt = 0;
    rep(i, 0, S.size()-1){
        if(S[i] == 'A'){
            cnt++;
        } else if (S[i] == 'B') {
            if (S[i+1] == 'C'){
                res += cnt;
                i++;
            } else {
                cnt =0;
            }
        } else {
            cnt = 0;
        }
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 640
#include <stdio.h>

int alg ( int input )
{
    int i, j, k, l, limit;
    int counter = 0;

    for ( i = 0; i < 10; i++ )
    {
        for ( j = 0; j < 10; j++ )
        {
            for ( k = 0; k < 10; k++ )
            {
                for ( l = 0; l < 10; l++ )
                {
                    if ( ( i + j + k + l ) == input )
                        counter++;
                }
            }
        }
    }

    return counter;
}

int main ( void )
{
    int input;
    while ( scanf( "%d", &input ) != EOF )
    {
        printf( "%d\n", alg( input ) );
    }
    return 0;
}

Measured memory_bytes: 592
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
using ll=long long;
using vec=vector<ll>;
using Graph = vector<vector<ll>>;
#define loop(i,n) for(ll i=0;i<n;i++)
#define Loop(i, m, n) for(ll i = m;i < n;i++)
#define pool(i,n) for(ll i=n-1;i>=0;i--)
#define Pool(i, m, n) for(ll i=n-1;i>=m;i--)
#define MAX 99999999999ll
#define MIN -99999999999ll
#define setbit bitset<8>
#define flagcount __builtin_popcount
#define flag(x) (1<<x)
#define flagadd(bit,x) bit|=flag(x)
#define flagpop(bit,x) bit&=~flag(x) 
#define flagon(bit,i) bit&flag(i)
#define flagoff(bit,i) !(bit & (1<<i))
#define all(v) v.begin(),v.end()
#define low2way(v,x) lower_bound(all(v),x)
#define high2way(v,x) upper_bound(all(v),x)
#define count2way(v,x) high2way(v,x)-low2way(v,x)
#define lower(v,x) low2way(v,x)-v.begin() //1番左が0、もし見つから無いならｎを出力
#define higher(v,x) high2way(v,x)-v.begin()-1 //1番左が0、もし見つからないならn-1を出力（注意）
#define putout(x) cout<<x<<endl
#define Gput(a,b) G[a].push_back(b)
ll ctoi(char c){
	if(c>='0'&&c<='9'){
		return c-'0';
	}
	return 0;
}
ll fact(ll x){
  ll y=1;
  for(ll i=1;i<=x;i++){
   y*=i;
   y%=1000000007;
  }
  return y;
}
int main() {
  ll n;
  cin>>n;
  vec a(n);
  loop(i,n){
  cin>>a[i];
  }
  map<ll,ll> count;
  loop(i,n){
  count[a[i]-1]++;
  count[a[i]]++;
  count[a[i]+1]++;
  }
  ll ans=0;
  Loop(i,-1,1000001){
  ans=max(ans,count[i]);
  }
  
  putout(ans);
  
}

Measured memory_bytes: 63488
#include<stdio.h>
int main(void)
{
  long int a,b,i,c,d,e;
  scanf("%ld",&a);
  scanf("%ld",&b);
  if(a>=b){
    c=a;
    d=b;
  }
  if(b>a){
    c=b;
    d=a;
  }
  for(i=1;i<=d;i++){
    e=c*i;
    if(e%d==0){
      printf("%ld\n",e);
      break;
    }
    if(e%d!=0){
      continue;
    }
  }
  return 0;
}

Measured memory_bytes: 128
n=int(input())
a=list(map(int,input().split()))
o=0
e=0
ee=0
for i in range(n):
    if a[i]%4==0:
        ee+=1
    elif a[i]%2==1:
        o+=1
    else:
        e+=1
if e%2==1:
    o+=1
if ee+1>=o:
    print("Yes")
else:
    print("No")

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

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

int main(){
	int n;
	ll k;
	cin >> n >> k;
	ll a[n];
	for(int i=0; i<n; i++) cin >> a[i];

	ll s[n+1];
	s[0]=0;
	for(int i=0; i<n; i++) s[i+1]=s[i]+a[i];
	for(int i=0; i<=n; i++) s[i]=(s[i]-i)%k;

	map<ll, ll> cnt;
	ll ans=0;
	for(int i=0; i<=n; i++){
		cnt[s[i]]++;
		if(i>=k) cnt[s[i-k]]--;
		ans+=cnt[s[i]]-1;
	}
	cout << ans << endl;
	return 0;
}

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

using namespace std;

#define int long long

#ifndef bhupixb
    #define var(...)
    #define stl(...)
#endif

#define rep(i,a,b) for (int i = a; i <= (int)b; ++i)
#define f first
#define s second

#define single_test


constexpr int mod = 1e9 + 7;

struct M {
    unsigned v;
    M(long long a = 0) : v((a %= mod) < 0 ? a + mod : a) {}
    M& operator+=(M r) { if ((v += r.v) >= mod) v -= mod; return *this; }
    M& operator-=(M r) { if ((v += mod - r.v) >= mod) v -= mod; return *this; }
    M& operator*=(M r) { v = (uint64_t)v * r.v % mod; return *this; }
};

uint32_t add(M a, M b) { return (a += b).v; }
uint32_t mul(M a, M b) { return (a *= b).v; }
uint32_t sub(M a, M b) { return (a -= b).v; }

const int maxn = 10002;
int32_t dp[maxn][100][2];

string s;
int d;

int32_t go(int pos, int rem, bool f = false) {
    if (pos == s.size()) {
        return rem == 0;
    }
    auto &ref = dp[pos][rem][f];
    if (ref != -1) {
        return ref;
    }
    int curDig = s[pos] - '0';
    int ans = 0;
    for (int i = 0; i < 10; ++i) {
        if (i > curDig && f == false) {
            break;
        }
        int new_rem = (rem + i);
        while (new_rem >= d) {
            new_rem -= d;
        }
        ans = add(ans, go(pos + 1, new_rem, f | (i < curDig)));
    }
    return ref = ans;
}

void solve() {
    memset(dp, -1, sizeof dp);
    cin >> s >> d;
    cout << sub(go(0, 0), 1);
}

signed main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    #ifndef single_test
        cin >> t;
    #endif
    for (int i = 1; i <= t; ++i) {
        // cout << "Case #" << i << ": ";
        solve();
    }

    return 0;
}

Measured memory_bytes: 12308
#include <iostream>
#include <stdio.h>
#include <bits/stdc++.h>
#include <vector>
#include <cmath>
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
using namespace std;

const ll MAX = 1000000;
const ll MOD = 1000000007;

ll fac[MAX];

// テーブルを作る前処理
/*
void COMinit() {
    fac[0] = fac[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
    }
}
*/

ll pow_kai(ll a,ll 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;
}

// 二項係数計算
ll COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    ll tmp=1;
    for(ll i=n;i>=n-k+1;i--) tmp = (tmp*i)%MOD;

    return (tmp * pow_kai(fac[k],MOD-2)) % MOD;
}



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

    amari=N%10;

    if(amari==3){
        cout << "bon" << endl;
    }else if(amari==0 or amari==1 or amari==6 or amari ==8){
        cout << "pon" << endl;
    }else{
        cout << "hon" << endl;
    }


 
    return 0;

}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll mod = 1000000007;
//const ll mod = 998244353;
const int inf = 1e9 + 10;
const ll INF = 1e18;
const ld EPS = 1e-10;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }



int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(25);

  ll n;
  string s;
  cin >> n >> s;

  map<char, ll> m;
  rep(i, n) {
    m[s[i]]++;
  }
  ll ans = m['R'] * m['G'] * m['B'];
  if (ans == 0) {
    cout << 0 << '\n';
    return 0;
  }
  FOR(i, 1, n) {
    rep(j, n) {
      if (j + 2 * i >= n) break;
      char a = s[j], b = s[j + i], c = s[j + 2 * i];
      if (a != b && a != c && b != c) ans--;
    }
  }
  cout << ans << '\n';
  

  
  return 0;
}

Measured memory_bytes: 3664
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long;

vector<vector<int>> tree(100001);
int dp[100001];

int dfs(int i) {
    int maxval = 0;
    for (auto x : tree[i]) {
        if (dp[x] == -1) {
            dp[x] = dfs(x) + 1;
        }
        if (dp[x] > maxval) {
            maxval = dp[x];
        }
    }
    return maxval;
}

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

    for (int i=0; i<m; i++) {
        int x, y;
        cin >> x >> y;
        tree[x].push_back(y);
    }

    for (int i=0; i<100001; i++) {
        dp[i] = -1;
    }

    int maxval = 0;
    for (int i=1; i<=n; i++) {
        int x = dfs(i);
        if (x > maxval) {
            maxval = x;
        }
    }

    cout << maxval << endl;

    return 0;
}

Measured memory_bytes: 8192
import itertools
N = int(input())
P = tuple(map(int, input().split()))
Q = tuple(map(int, input().split()))

for i, lst in enumerate(itertools.permutations(range(1,N+1))):
    if lst == P:
        p = i
    if lst == Q:
        q = i
print(abs(p-q))


Measured memory_bytes: 3060
#include <bits/stdc++.h>
        using namespace std;
   #define int long long
const int MAX = 510000;
const int MOD = 1000000007;

 
     signed main(){
    int n,m;
    cin>>n>>m;
    int a[n],b[n],c[n];
    map<int,int> t,y;
    t[0]=1;y[0]=1;
    for(int i=0;i<n;i++){
         cin>>a[i]>>b[i]>>c[i];
       t[a[i]]=1;
       t[b[i]]=1;
       y[c[i]]=1;  
    }
    int d[m],e[m],f[m];
    for(int i=0;i<m;i++){
         cin>>d[i]>>e[i]>>f[i];
         t[d[i]]=1;
         y[e[i]]=1;
         y[f[i]]=1;

    }
    vector<int> tx,yx;
    for(auto&& i : t){
         if(!tx.empty())tx[tx.size()-1]+=i.first;
         i.second=tx.size();
         tx.push_back(0);
         tx.push_back(-i.first);
    }
    tx.pop_back();
    for(auto&& i : y){
         if(!yx.empty())yx[yx.size()-1]+=i.first;
         i.second=yx.size();
         yx.push_back(0);
         yx.push_back(-i.first);
    }
    yx.pop_back();
    bool used[tx.size()][yx.size()];
     for(int i=0;i<tx.size();i++)fill(used[i],used[i]+yx.size(),false);
     for(int i=0;i<n;i++){
          int p=t[a[i]],q=t[b[i]],r=y[c[i]];
          for(int j=p;j<=q;j++)used[j][r]=true;
     }
     for(int i=0;i<m;i++){
          int p=t[d[i]],q=y[e[i]],r=y[f[i]];
          for(int j=q;j<=r;j++)used[p][j]=true;
     }

     queue<pair<int,int>> que;
     int ans=0;
     used[t[0]][y[0]]=true;
     que.push({t[0],y[0]});
     while(!que.empty()){
          pair<int,int> p=que.front();
          que.pop();
          if(p.first==0||p.first==tx.size()-1||p.second==0||p.second==yx.size()-1){
               cout<<"INF"<<endl;
               return 0;
          }
          if(!used[p.first-1][p.second]){
               ans+=tx[p.first-1]*yx[p.second];
               used[p.first-1][p.second]=true;
               que.push({p.first-1,p.second});
          }
          if(!used[p.first+1][p.second]){
               ans+=tx[p.first+1]*yx[p.second];
               used[p.first+1][p.second]=true;
               que.push({p.first+1,p.second});
          }
          if(!used[p.first][p.second-1]){
               ans+=tx[p.first]*yx[p.second-1];
               used[p.first][p.second-1]=true;
               que.push({p.first,p.second-1});
          }
          if(!used[p.first][p.second+1]){
               ans+=tx[p.first]*yx[p.second+1];
               used[p.first][p.second+1]=true;
               que.push({p.first,p.second+1});
          }
     }
     cout<<ans<<endl;
     return 0;

      }

        

Measured memory_bytes: 39344
#include <bits/stdc++.h>
using namespace std;
#define ll long long int 
#define ld double
#define mp make_pair
#define pb push_back
#define mod 1000000007
#define ff first
#define ss second
#define pll pair <ll,ll>
#define nl "\n"
ll n,W;
ll dp[102][100005];
ll w[102],v[102];

ll rec(ll idx,ll cw)
{
	if(idx==n)
		return 0;
	if(dp[idx][cw]==-1)
	{
		if(cw+w[idx]<=W)
			dp[idx][cw]=max(rec(idx+1,cw+w[idx])+v[idx],rec(idx+1,cw));
		else
			dp[idx][cw]=rec(idx+1,cw);
	}
	return dp[idx][cw];
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin>>n>>W;
	ll i;
	for(i=0;i<n;i++)
		cin>>w[i]>>v[i];
	for(i=0;i<102;i++)
		for(ll j=0;j<100005;j++)
			dp[i][j]=-1;
	rec(0,0);
	cout<<dp[0][0]<<nl;
	return 0;
}

Measured memory_bytes: 80000
#include<iostream>
using namespace std;
int main() {
	int a, b, t;
	cin >> a >> b >> t;
	int bb = 0;
	int aa = 0;
	while (aa + a <= t) {
		bb = bb + b;
		aa = aa + a;
	}
	cout << bb << endl;
	return 0;

}

Measured memory_bytes: 256
#include <string.h>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

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

#define SORT(V) sort((V).begin(), (V).end())

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

int main() {
  string S;
  cin >> S;
  int A = S[0] - '0';
  int B = S[1] - '0';
  int C = S[2] - '0';
  int D = S[3] - '0';
  REP(i, 1 << 3) {
    int sum = A;
    if (i & 1) sum += B; else sum -= B;
    if (i & 2) sum += C; else sum -= C;
    if (i & 4) sum += D; else sum -= D;
    if (sum == 7) {
      cout << A << ((i & 1) ? "+" : "-")
           << B << ((i & 2) ? "+" : "-")
           << C << ((i & 4) ? "+" : "-")
           << D << "=7" << endl;
      break;
    }
  }
}


Measured memory_bytes: 256
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;

class Main {
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static PrintWriter pw = new PrintWriter(System.out);
    public static String line;
    public static StringTokenizer st;
    public static ArrayList<ArrayList<Integer>> adjList;
    public static int[] dx = {-1, 0, 1, 0, -1, 1, 1, -1};
    public static int[] dy = {0, 1, 0, -1, 1, 1, -1, -1};
    public static int INF = 0x3f3f3f3f;
    public static long LINF = 0x3f3f3f3f3f3f3f3fL;
    public static int MOD = 1000000007;

    public static void main(String[] args) throws Exception{
        String s = br.readLine();
        TreeSet<Character> d = new TreeSet<Character>();
        for(int i = 0; i < s.length(); i++){
            d.add(s.charAt(i));
        }

        int best = INF;
        if(d.size() == 1){
            best = 0;
        }
        for(Character t : d){
            boolean f = true;
            char[] A = s.toCharArray();
            int ans = 0;
            while(f){
                f = false;
                char[] B = new char[A.length-1];
                for(int i = 0; i < B.length; i++){
                    if(A[i] == t || A[i+1] == t){
                        B[i] = t;
                    } else{
                        B[i] = A[i];
                        f = true;
                    }
                }
                ans++;
                A = B;
            }
            best = Math.min(best, ans);
        }
        pw.print(best + "\n");
        
        pw.close(); 
        br.close();
    }
}

Measured memory_bytes: 21588