akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <bitset>
#include <set>
#include <tuple>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
#define all(i,n) (i),(i+n)

int dx4[4]={1,0,-1,0};
int dy4[4]={0,-1,0,1};
int dx8[8]={1,0,-1,1,-1,1,0,-1};
int dy8[8]={1,1,1,0,0,-1,-1,-1};

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

const int INF = 1e9;
const ll LLINF = 1e18;
const int MAX_V = 1e6+1;
const ll mod = 1000000007;

// --------------------------------------
int n;
int a[100];
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> n;
  int sum = 0;
  REP(i, n) {
    cin >> a[i];
    sum += a[i];
  }

  int b = INF;
  int b_sum = 0;
  REP(i, n) {
    int c = abs(sum - ((b_sum + a[i]) * 2));
    if(c > b) {
      break;
    } else {
      b_sum += a[i];
      b = c;
    }
  }

  cout << abs(b_sum - (sum - b_sum)) << endl;
}


Measured memory_bytes: 256
import java.util.*;

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

		int n=sc.nextInt();
		String k=String.valueOf(n);
		String kk[]=k.split("");
		boolean ans=true;
		if(kk[0].equals(kk[2])){
			System.out.println("Yes");
		}else{
			System.out.println("No");
		}



  }
}


Measured memory_bytes: 21844
import java.util.Scanner;

public class Main {

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

		int n = stdIn.nextInt();
		int m = stdIn.nextInt();
		int max = m;
		int now = max;
		boolean flag = false;
		for(int i=0;i<n;i++){
			int in = stdIn.nextInt();
			int out = stdIn.nextInt();
			now += in;
			now -= out;
			if(now<0){
				flag = true;
			}
			if(max<now) max = now;
		}
		if(flag) System.out.println("0"); else System.out.println(max);
	}
}

Measured memory_bytes: 40336
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;cin>>n;
  vector<int>a(n);
  vector<int>b(n);
  vector<int>c(n-1);
  int man=0;
  for(int i=0;i<n;++i)cin>>a[i];
  for(int i=0;i<n;++i){
    cin>>b[i];
    man+=b[i];
  }
  for(int i=0;i<n-1;++i)cin>>c[i];
  
  for(int i=1;i<n;++i){
    if(a[i]==(a[i-1]+1)){
      man+=c[a[i]-2];
    }
  }
  cout<<man<<endl;
}

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

//typedef
typedef unsigned int UINT;
typedef unsigned long long ULL;
typedef long long LL;
typedef long double LD;
typedef pair<LL, LL> PLL;
typedef tuple<LL, LL, LL> TLL3;
typedef tuple<LL, LL, LL, LL> TLL4;
typedef set<LL, greater<LL> > setdownLL;
#define PQ priority_queue
typedef PQ<LL, vector<LL>, greater<LL> > pqupLL;
//container utill
#define ALL(v) (v).begin(),(v).end()
#define CR [](auto element1, auto element2){return element1>element2;}
#define LB lower_bound
#define UP upper_bound
#define PB push_back
#define MP make_pair
#define MT make_tuple
//constant
#define PI 3.141592653589793

template<class Abel> struct BIT{
    vector<Abel> dat;
    long long n;

    BIT(long long n_origin, Abel SUM_UNITY):dat(n_origin +1,SUM_UNITY), n(n_origin){}

    Abel sum_from_first(long long i){//[1,i]
        Abel s=0;
        while(i>0){
            s+=dat[i];
            i-= (i&(-i));
        }
        return s;
    }

    Abel sum(long long i, long long j){//[i,j)
        Abel vl = sum_from_first(i-1);
        Abel vr = sum_from_first(j-1);
        return vr-vl;
    }

    void add(long long i, Abel x){
        while(i <= n){
            dat[i] += x;
            i += (i&(-i));
        }
    }
};

int main(){
    //input
    LL N,K;
    cin >> N >> K;
    long long i;
    LL A[N+1];
    A[0]=0;
    for(i=1; i<=N; i++){
        cin >> A[i];
        A[i]-=K;
    }

    //calc
    long long n=N+1;
    long long a[n+1];
    vector<pair<long long, long long> > a_ind;
    a_ind.resize(n);
    for(i=0; i<n; i++){
        if(i==0){
            a[i]=A[i];
        }else{
            a[i]=A[i]+a[i-1];
        }
        a_ind[i]=make_pair(a[i],i);
    }
    sort(a_ind.begin(),a_ind.end());
    for(i=0; i<n; i++){
        a[a_ind[i].second]=i+1;
    }
    long long ans=0;
    BIT<long long> BIT(n,0);
    for(i=0; i<n; i++){
        ans += i-BIT.sum_from_first(a[i]);
        BIT.add(a[i],1);
    }

    //output
    cout << ((N+1LL)*N)/2LL-ans << endl;
    system("pause");
    return 0;
}

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

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using usize = std::size_t;
using namespace std;
#define rep(i, max) for(i32 i = 0; i < (i32)max; ++i)
#define loop while(true)
#define allOf(collection) collection.begin(), collection.end()

unique_ptr<string> readLine() { unique_ptr<string> line(new string()); getline(cin, *line); return line; }
template<typename T1, typename T2> pair<T1, T2> readPair() { T1 res1; cin >> res1; T2 res2; cin >> res2; readLine(); return make_pair(res1, res2); }
template<typename T> unique_ptr<vector<T>> readVector(usize num, bool isForIndex = false) { unique_ptr<vector<T>> list(new vector<T>(num)); rep(i, num) { cin >> (*list)[i]; if (isForIndex) --(*list)[i]; } readLine(); return list; }
void readValues() { readLine(); }
template<typename H, typename... T> void readValues(H& head, T&&... tails) { H a; cin >> a; head = a; readValues(forward<T>(tails)...); }
void writeLine() { cout << endl; }
template<typename T> void write(const T& arg) { cout << arg; }
template<typename T> void writeLine(const vector<T>& arg) { if (arg.empty()) { writeLine(); return; } write(arg[0]); for (int i = 1; i < arg.size(); ++i) { write(" "); write(arg[i]); } writeLine(); }
template<typename T> void writeLine(const T& arg) { cout << arg << endl; }
void program();
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    program();
}

void program() {
    i32 n;
    readValues(n);
    auto set1 = set<string>();
    rep(i, n) {
        set1.insert(*readLine());
    }
    writeLine(set1.size());
}

Measured memory_bytes: 19252
import java.util.*;

public class Main{
  public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    if(a > b){
      System.out.println(a - 1);
    }else{
      System.out.println(a);
    }
  }
}

Measured memory_bytes: 21588
#include <bits/stdc++.h>
using namespace std;
int a[3][3];
bool f[3][3];
int main(){
	memset(f,0,sizeof(f));
	int n,i,j,k,m;
	bool ff=false;
	for(i=0;i<3;i++){
		for(j=0;j<3;j++){
			cin>>a[i][j];
		}
	}
	cin>>n;
	for(i=1;i<=n;i++){
		cin>>m;
		for(k=0;k<3;k++){
			for(j=0;j<3;j++){
				if(a[k][j]==m){
					f[k][j]=true;
				}
			}
		}
	}
	if(f[0][0]==true&&f[0][1]==true&&f[0][2]==true) ff=true;
	if(f[1][0]==true&&f[1][1]==true&&f[1][2]==true) ff=true;
	if(f[2][0]==true&&f[2][1]==true&&f[2][2]==true) ff=true;
	if(f[0][0]==true&&f[1][0]==true&&f[2][0]==true) ff=true;
	if(f[0][1]==true&&f[1][1]==true&&f[2][1]==true) ff=true;
	if(f[0][2]==true&&f[1][2]==true&&f[2][2]==true) ff=true;
	if(f[0][0]==true&&f[1][1]==true&&f[2][2]==true) ff=true;
	if(f[0][2]==true&&f[1][1]==true&&f[2][0]==true) ff=true;
	if(ff==true) cout<<"Yes";
	else cout<<"No";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define fr(i,n) for(i=0;i<n;i++)
#define F first
#define S second
#define fast std::ios_base::sync_with_stdio(false)
#define mod 1000000007
#define pi 3.14159265
int main() {
	fast;
	lli a,b;
	cin>>a>>b;
	if((a==1&&b==2)||(a==2&&b==1))
	{
		cout<<3;
	}
	else if((a==1&&b==3)||(a==3&&b==1))
	{
		cout<<2;
	}
	else
		cout<<1;

	
	return 0;
}

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

using namespace std;

class SieveOfEratosthenes {
 private:
  std::vector<int> sieve;

 public:
  SieveOfEratosthenes(int n) : sieve(n + 1) {
    std::iota(sieve.begin(), sieve.end(), 0);
    for (int i = 2; i * i < n + 1; i++) {
      if (sieve[i] != i) continue;
      for (int j = i * i; j < n + 1; j += i) {
        if (sieve[j] == j) sieve[j] = i;
      }
    }
  }

  bool is_prime(int x) const { return x != 0 && x != 1 && sieve[x] == x; }

  std::vector<int> factor(int x) const {
    std::vector<int> res;
    while (x > 1) {
      res.emplace_back(sieve[x]);
      x /= sieve[x];
    }
    return res;
  }
};

template <typename T>
std::map<T, int> count(std::vector<T>& vec) {
  std::map<T, int> res;
  for (const T& x : vec) {
    res[x]++;
  }
  return res;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N;
  cin >> N;
  vector<int> A(N);
  for (auto&& e : A) {
    cin >> e;
  }
  SieveOfEratosthenes soe(10000000);
  map<int, int> mp;
  for (int a : A) {
    auto primes = soe.factor(a);
    auto mprimes = count(primes);
    for (const auto& [key, value] : mprimes) {
      mp[key]++;
    }
  }
  bool pairwise = true;
  for (const auto& [key, value] : mp) {
    if (value > 1) pairwise = false;
  }
  if (pairwise) {
    cout << "pairwise coprime" << '\n';
  } else {
    int g = 0;
    for (const auto& e : A) {
      g = gcd(g, e);
    }
    if (g == 1) {
      cout << "setwise coprime" << '\n';
    } else {
      cout << "not coprime" << '\n';
    }
  }
  return 0;
}


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

using vi = vector<int>;

int gcd(int N, int M){return M?gcd(M,N%M):N;}

int main(){
    int N;
    cin >> N;
    vi A(N);
    for(int i=0;i<N;i++) cin >> A[i];
    vi GCD_left(N,0); GCD_left[0] = A[0];
    vi GCD_right(N, 0); GCD_right[N-1] = A[N-1];

    for(int i=1;i<N;i++){
        GCD_left[i] = gcd(A[i],GCD_left[i-1]);
    }
    for(int i=N-2;i>=0;i--){
        GCD_right[i] = gcd(A[i], GCD_right[i+1]);
    }

    int ans = max(GCD_right[1], GCD_left[N-2]);
    for(int i=1;i<N-1;i++){
        ans = max(ans,gcd(GCD_left[i-1],GCD_right[i+1]));
    }
    cout << ans << endl;
}

Measured memory_bytes: 1408
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 100;
const int INF = 1 << 30;

/* typedef */

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

typedef vector<pii> vpii;

struct Stat {
  int d, i;
  Stat() {}
  Stat(int _d, int _i) { d = _d, i = _i; }

  bool operator<(const Stat& s0) const { return d > s0.d; }
};

/* global variables */

int n, m, st, g1, g2;
vpii nbrs[MAX_N], rnbrs[MAX_N];
int dists[MAX_N];

/* subroutines */

int min_dist(int mp, int gl, vpii *nbrs) {
  int mind = INF;

  for (int i = 0; i < n; i++) dists[i] = INF;
  dists[mp] = 0;

  priority_queue<Stat> q;
  q.push(Stat(0, mp));

  while (! q.empty()) {
    Stat u = q.top();
    q.pop();

    //printf("u.d=%d, u.i=%d\n", u.d, u.i);
    
    if (u.d != dists[u.i]) continue;

    if (u.i == gl) {
      if (mind > u.d) mind = u.d;
      break;
    }

    vpii& nbru = nbrs[u.i];
    for (vpii::iterator vit = nbru.begin(); vit != nbru.end(); vit++) {
      int vi = vit->first;
      int vd = u.d + vit->second;
      //printf("  vd=%d, vi=%d\n", vd, vi);

      if (dists[vi] > vd) {
	dists[vi] = vd;
	q.push(Stat(vd, vi));
      }
    }
  }

  return mind;
}

/* main */

int main() {
  for (;;) {
    cin >> n >> m >> st >> g1 >> g2;
    if (n == 0) break;
    st--, g1--, g2--;

    for (int i = 0; i < n; i++)
      nbrs[i].clear(), rnbrs[i].clear();
    
    while (m--) {
      int b1, b2, c;
      cin >> b1 >> b2 >> c;
      b1--, b2--;
      nbrs[b1].push_back(pii(b2, c));
      rnbrs[b2].push_back(pii(b1, c));
    }

    int mind = INF;

    for (int mp = 0; mp < n; mp++) {
      //printf("mp=%d:\n", mp);

      int mind_st = min_dist(mp, st, rnbrs);
      //printf("  mind_st=%d\n", mind_st);
      if (mind_st >= INF) continue;

      int mind_g1 = min_dist(mp, g1, nbrs);
      //printf("  mind_g1=%d\n", mind_g1);
      if (mind_g1 >= INF) continue;

      int mind_g2 = min_dist(mp, g2, nbrs);
      //printf("  mind_g2=%d\n", mind_g2);
      if (mind_g2 >= INF) continue;

      int dsum = mind_st + mind_g1 + mind_g2;
      if (mind > dsum) mind = dsum;
    }

    cout << mind << endl;
  }

  return 0;
}

Measured memory_bytes: 1256
#include<stdio.h>
int main(void){
	int n, rem, i, j, k, val,
	    s[13] = {0}, scnt = 13, h[13] = {0}, hcnt = 13, c[13] = {0}, ccnt = 13, d[13] = {0}, dcnt = 13;
	char mark;
	
	scanf("%d\n", &n);
	for(i = 0; i < n; i++){
		scanf("%c", &mark);
		scanf("%d\n", &val);
		val -= 1;
		switch(mark){
			case 'S':
			s[val] = 1;
			scnt--;
			break;
			case 'H':
			h[val] = 1;
			hcnt--;
			break;
			case 'C':
			c[val] = 1;
			ccnt--;
			break;
			case 'D':
			d[val] = 1;
			dcnt--;
			break;
		}
	}
	
	for(k = 0; k < 13; k++){
		if(scnt == 0){
			break;
		}
		if(s[k] == 0){
			printf("S %d\n", k+1);
			s[k] = 1;
			scnt--;
		}
	}
	for(k = 0; k < 13; k++){
		if(hcnt == 0){
			break;
		}
		if(h[k] == 0){
			printf("H %d\n", k+1);
			h[k] = 1;
			hcnt--;
		}
	}
	for(k = 0; k < 13; k++){
		if(ccnt == 0){
			break;
		}
		if(c[k] == 0){
			printf("C %d\n", k+1);
			c[k] = 1;
			ccnt--;
		}
	}
	for(k = 0; k < 13; k++){
		if(dcnt == 0){
			break;
		}
		if(d[k] == 0){
			printf("D %d\n", k+1);
			d[k] = 1;
			dcnt--;
		}
	}
	return 0;
}


Measured memory_bytes: 2124
#include<iostream>
#include<vector>
#include<algorithm>

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


Measured memory_bytes: 256
#!/usr/bin/env ruby

manhattan = 0
euclidean = 0
l3distance = 0
chebyshev = 0
tempArray = []

loop_number = gets.to_i
vectorA = gets.split.map(&:to_i)
vectorB = gets.split.map(&:to_i)

loop_number.times do |index|
    points = (vectorA[index] - vectorB[index]).abs
    manhattan += points
    euclidean += points ** 2.0
    l3distance += points ** 3.0
    tempArray << points
end

euclidean = euclidean ** (1/2.0)
l3distance = l3distance ** (1/3.0)
chebyshev = tempArray.max
puts manhattan.to_f,euclidean,l3distance,chebyshev.to_f


Measured memory_bytes: 6956
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
int main()
{
    int a[100005]={0},c[100005]={0};char b[100005];
    scanf("%s",b);int len=strlen(b);
    for(int i=0;i<len;i++)
    {
        a[i]+=1;
        if(b[i]=='R'&&b[i+1]=='R')
        {a[i+1]+=a[i];a[i]=0;}
    }
    for(int i=len-1;i>=0;i--)
        if(b[i]=='L'&&b[i-1]=='L')
        {a[i-1]+=a[i];a[i]=0;}
    for(int i=0;i<len;i++)
    {
        if(a[i]==0) continue;
        if(a[i]==1) {c[i]+=1;continue;}
        if(b[i]=='R') {c[i]+=a[i]-a[i]/2;c[i+1]+=a[i]/2;}
        if(b[i]=='L') {c[i-1]+=a[i]/2;c[i]+=a[i]-a[i]/2;}
    }
    for(int i=0;i<len-1;i++)
        printf("%d ",c[i]);
    printf("%d\n",c[len-1]);
    return 0;
}


Measured memory_bytes: 1408
#include <stdio.h>  
#include <string.h>  
#include <stdlib.h>  
#include <iostream>  
#include <algorithm>  
#include <time.h>  
#include<cstdio>
#include<vector>
#include<functional>


using namespace std;
long long n, a, b, c, d;


int main() {

	scanf("%lld%lld%lld%lld%lld", &n, &a, &b, &c, &d);
	for (int i = 0; i != n; ++i) {
		if ((n * c - c - i * (c + d) <= b - a) && (b - a <= n * d - d - i * (c + d))) {
			printf("YES");
			return 0;
		}
	}
	printf("NO");
	return 0;
}


Measured memory_bytes: 256
cnt = 0
m = 0
gap = []

def insertion_sort(nums, n, g):
    global cnt
    for i in range(1, n):
        key = nums[i]
        j = i - g
        while j >= 0 and nums[j] > key:
            nums[j + g] = nums[j]
            j -= g
            cnt += 1
        nums[j + g] = key

def shell_sort(nums, n):
    global m
    g = 0
    while True:
        g = g * 3 + 1
        if g > n:
            break
        gap.append(g)
    gap.reverse()
    m = len(gap)
    for i in range(m):
        insertion_sort(nums, n, gap[i])

n =  int(input())
nums = []
for i in range(n):
    nums.append(int(input()))
shell_sort(nums, n)

print(m)
print(' '.join(map(str, gap)))
print(cnt)
for i in range(n):
    print(nums[i])



Measured memory_bytes: 45520
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;

int main()
{
	int x, y, z;
	cin>>x>>y>>z;
	swap(x, y);
	swap(x, z);
	cout<<x<<" "<<y<<" "<<z<<endl;
	return 0;
}


Measured memory_bytes: 256
//优化
#pragma GCC optimize(2)
//C
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
//C++
#include<algorithm>
#include<iostream>
#include<istream>
#include<iomanip>
#include<cstdio>
#include<stack>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<set>
//宏定义
#define it set<ll>::iterator
#define N 1010
//定义+命名空间
typedef long long ll;
typedef unsigned long long ull;
const int mod = 998244353;
const int INF = 1e9;
const int maxn = 1e6 + 5;
using namespace std;
//全局变量//
//函数区//
ll max(ll a, ll b) { return a > b ? a : b; }
ll min(ll a, ll b) { return a < b ? a : b; }
bool judge(ll x, ll y) {
    if (x >= 0 && y >= 0) return 1;
    if (x <= 0 && y <= 0) return 1;
    return 0;
}
//主函数//
int main() {
 
    ll x, y;
    cin >> x >> y;
 
    if (y > x) {
        if (judge(x, y))
            cout << y - x << endl;
        else {
            ll temp = abs(x + y);
            cout << temp + 1 << endl;
        }
    }
    else if (x >= 0 && y >= 0) {
        if (y != 0)
            cout << x - y + 2 << endl;
        else cout << x - y + 1 << endl;
    }
    else if (x <= 0 && y <= 0) {
        if (x != 0)
            cout << x - y + 2 << endl;
        else cout << x - y + 1 << endl;
    }
    else if (x >= 0 && y <= 0) {
        ll temp = abs(x + y);
        cout << temp + 1 << endl;
    }
    return 0;
}
//分割线---------------------------------QWQ
/*
 
1 2 5
4 3 1
 
1 2 4
5 2 1
*/
 
/*
 
f(n) = ln(n) + C + 1 / 2 * n
double C = 0.57721566490153286060651209;
 
*/

Measured memory_bytes: 256
import sys
input = sys.stdin.readline



M, W = map(int, input().split())                                # M: 品物の種類 W: 重量制限
single = True                                                   # True = 重複なし

price_list = [0]
weight_list = [0]
for _ in range(M):
    price, weight = map(int, input().split())
    price_list.append(price)
    weight_list.append(weight)


################################################################################################################################################

V = sum(price_list)
dp_max = W + 1                                                  # 総和重量の最大値


dp = [[dp_max] * (V + 1) for _ in range(M + 1)]                 # 左端と上端の境界条件で W, M を一個ずつ多めに取る
""" dp[item <= M ][weight <= V] = 価値を固定した時の"最小"重量 """

for item in range(M+1):                                         # 左端の境界条件
    dp[item][0] = 0                                             # 価値 0 を実現するのに必要な品物の個数は 0 個

# for weight in range(W+1):                                     # 上端の境界条件
#     dp[0][weight] = dp_min                                    # 0 種類の品物で実現できる価値総額は存在しない　（dpの初期化で自動的に課せる場合が多い）


for item in range(1,M+1):                                       # 境界条件を除いた M 回のループ（※ f[item] = g.f[item-i] の漸化式なので、list index out of range となる）
    for price in range(1, V+1):
        if price < price_list[item]:                            # price (総価値) < price_list[item] (品物の価値) の時は無視してよい
            dp[item][price] = dp[item - 1][price]
        else:
            temp = dp[item - single][price - price_list[item]] + weight_list[item]  # single = True: 重複なし
            if temp < dp[item-1][price]:                        # min(dp[item-1][price], temp)
                dp[item][price] = temp
            else:
                dp[item][price] = dp[item-1][price]

print(max(price for price in range(V+1) if dp[M][price] <= W))


Measured memory_bytes: 13480
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <functional>
#include <stack>
#include <numeric>
typedef long long ll;
using namespace std;
const int MOD = (int)1e9 + 7;
const ll INF = (ll)1e18 + 7;
#define int long long
#define all(vec) vec.begin(), vec.end()
#define dbg(x) cerr << #x << " = " << (x) << endl
#define yn(b) cout << ((b) ? "Yes" : "No") << endl
#define YN(b) cout << ((b) ? "YES" : "NO") << endl
#define isEven(t) t % 2 == 0

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

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

	string S;
	cin>>S;
	S[3]='8';
	cout << S << endl;

	return 0;
}

Measured memory_bytes: 256
package main

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

func main() {
	sc = initScanner(os.Stdin)
	n, d := scanInt(sc), scanFloat64(sc)
	fmt.Println(solve(n, d))
}

func solve(n int, d float64) int {
	var x, y float64
	var cnt int
	for i := 0; i < n; i++ {
		x, y = scanFloat64(sc), scanFloat64(sc)
		if math.Sqrt(x*x+y*y) <= d {
			cnt++
		}
	}
	return cnt
}

// --------------- BASE DEFINITIONS ---------------

const (
	initialBufSize = 100000
	maxBufSize     = 1000000
)

var sc *bufio.Scanner

func initScanner(r io.Reader) *bufio.Scanner {
	buf := make([]byte, initialBufSize)

	sc := bufio.NewScanner(r)
	sc.Buffer(buf, maxBufSize)
	sc.Split(bufio.ScanWords)
	return sc
}

func scanInt(sc *bufio.Scanner) int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return i
}

func scanIntSlice(sc *bufio.Scanner, n int) []int {
	is := make([]int, n)
	for i := 0; i < n; i++ {
		is[i] = scanInt(sc)
	}

	return is
}

func scanFloat64(sc *bufio.Scanner) float64 {
	sc.Scan()
	f, _ := strconv.ParseFloat(sc.Text(), 64)
	return f
}

func scanFloat64Slice(sc *bufio.Scanner, n int) []float64 {
	fs := make([]float64, n)
	for i := 0; i < n; i++ {
		fs[i] = scanFloat64(sc)
	}

	return fs
}

func scanString(sc *bufio.Scanner) string {
	sc.Scan()
	return sc.Text()
}

func scanStringSlice(sc *bufio.Scanner, n int) []string {
	ss := make([]string, n)
	for i := 0; i < n; i++ {
		sc.Scan()
		ss[i] = sc.Text()
	}

	return ss
}

func abs(n int) int {
	if n < 0 {
		return -n
	}
	return n
}


Measured memory_bytes: 5000
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n;
pair<int,int> a[N];
string s;
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i].first>>a[i].second;
    for(int i=1;i<=n-2;i++){
        if(a[i].first == a[i].second && a[i+1].first == a[i+1].second && a[i+2].first == a[i+2].second){
            cout<<"Yes"<<endl;
            return;
        }
    }
    cout<<"No"<<endl;
}
int main(){
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}

Measured memory_bytes: 3636
package main

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

var sc = bufio.NewScanner(os.Stdin)

func init() {
	sc.Split(bufio.ScanWords)
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func main() {
	N := nextInt()
	B := make([]int, N-1)

	for i := 0; i < N-1; i++ {
		B[i] = nextInt()
	}

	total := B[0]

	for i := 0; i < N-2; i++ {
		r:=min(B[i], B[i+1])
		total += r
	}
	total += B[len(B) -1]

	fmt.Printf("%d", total)
}

func min(a, b int) int {
	if a < b {
		return a
	}

	return b
}


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

string itos(int x){
  string res;
  while(x){
    res+=x%10+'0';
    x/=10;
  }
  reverse(res.begin(),res.end());
  return res;
}

int main(){
  string s[2];
  int n,x;
  while(1){
    cin>>n;
    if(!n)break;
    cin>>s[0];
    x=0;
    while(n--){
      s[!x].clear();
      char num;
      int cnt=0;
      s[x]+='x';
      for(int i=0;i<s[x].size()-1;i++){
	num=s[x][i];
	if(s[x][i]!=s[x][i+1])
	  s[!x]+=itos(cnt+1)+num,cnt=0;
	else cnt++;
      }
      x=!x;
    }
    cout<<s[x]<<endl;
    s[!x].clear();
  }
  return 0;
}

Measured memory_bytes: 1336
#include <stdio.h>

#define N 101

int main(){
	int G[N][N], A[N], flag[N], n, i, j, k=1, min=0, value, sum=0;

	scanf("%d", &n);

	//initialize
	for(i = 0; i < n; i++)
		for(j = 0; j < n; j++)
			scanf("%d", &G[i][j]);

	A[0] = 0;
	flag[0] = 1;

	for(i = 1; i < n; i++) flag[i] = 0;

	//definition tree
	while(1){
		value = 2000;

		for(i = 0; i < k; i++){
			for(j = 0; j < n; j++){
				if(G[A[i]][j] < value && G[A[i]][j] != -1 && flag[j] != 1){
					value = G[A[i]][j];
					min = j;
				}
			}
		}

		if(k != n){
			A[k] = min;
			flag[min] = 1;
			sum += value;
			k++;
		}
		else break;
	}

	printf("%d\n", sum);

	return 0;
} 

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

using namespace std;

int main(){
    int N, Acount, Bcount, ABcount, ans;;
    cin >> N;

    Acount = 0;
    Bcount = 0;
    ABcount = 0;
    ans = 0;
    
    for(int i = 0; i < N; i++)
    {
        string s;
        cin >> s;

        if (s[0] == 'B' && s[s.size()-1] == 'A') {
            ABcount += 1;
        }

        if (s[0] != 'B' && s[s.size()-1] == 'A') {
            Acount += 1;
        }

        if (s[0] == 'B' && s[s.size()-1] != 'A') {
            Bcount += 1;
        }
        
        for(int j = 0; j < s.size()-1; j++)
        {
            
            if (s[j] == 'A' && s[j+1] == 'B') {
                ans += 1;
            }
            
        }
        

    }

    if (ABcount == 0 && Acount + Bcount != 0){
        ans += min(Acount, Bcount);
    }else if (ABcount != 0 && Acount + Bcount == 0){
        ans += ABcount - 1;
    }else if (ABcount != 0 && Acount + Bcount != 0){
        ans += ABcount + min(Acount, Bcount);
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using static Input;

public class Prog
{
    private const int INF = 1000000007;
    private const long INFINITY = 9223372036854775807;
    private struct Pair { public int x, y; public Pair(int xx, int yy) { x = xx; y = yy; } }
    private static int[] dx = { 1, 0, -1, 0 };
    private static int[] dy = { 0, -1, 0, 1 };
    public static void Main()
    {
        int H = NextInt();
        int W = NextInt();
        int N = NextInt();
        int sr = NextInt();
        int sc = NextInt();
        string S = NextString();
        string T = NextString();

        int Left = 1;
        int Right = W;
        int Up = 1;
        int Down = H;

        for (int i = N - 1; i >= 0; i--)
        {
            if (T[i] == 'R') Left = Math.Max(Left - 1, 1);
            else if (T[i] == 'L') Right = Math.Min(Right + 1, W);
            else if (T[i] == 'U') Down = Math.Min(Down + 1, H);
            else if (T[i] == 'D') Up = Math.Max(Up - 1, 1);

            if (S[i] == 'R') Right--;
            else if (S[i] == 'L') Left++;
            else if (S[i] == 'U') Up++;
            else if (S[i] == 'D') Down--;

            if (Left > Right || Up > Down) { Console.WriteLine("NO"); return; }
        }
        Console.WriteLine((Left <= sc && sc <= Right && Up <= sr && sr <= Down ? "YES" : "NO"));
    }
}

public class Input
{
    private static Queue<string> q = new Queue<string>();
    private static void Confirm() { if (q.Count == 0) foreach (var s in Console.ReadLine().Split(' ')) q.Enqueue(s); }
    public static int NextInt() { Confirm(); return int.Parse(q.Dequeue()); }
    public static long NextLong() { Confirm(); return long.Parse(q.Dequeue()); }
    public static char NextChar() { Confirm(); return char.Parse(q.Dequeue()); }
    public static string NextString() { Confirm(); return q.Dequeue(); }
    public static double NextDouble() { Confirm(); return double.Parse(q.Dequeue()); }
    public static int[] LineInt() { return Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); }
    public static long[] LineLong() { return Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); }
    public static string[] LineString() { return Console.ReadLine().Split(' ').ToArray(); }
    public static double[] LineDouble() { return Console.ReadLine().Split(' ').Select(double.Parse).ToArray(); }
}


Measured memory_bytes: 14176
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <utility>

#include <cassert>
#include <cmath>
#include <cstdio>

using namespace std;

#define fi first
#define se second
#define mkp make_pair
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define FOR(i,a,b) for(ll i=(a); i < (b); i++)
#define RFOR(i,a,b) for(ll i=(b)-1; i >= (a); i--)
#define rep(i,n) FOR(i,0,(n))
#define rrep(i,n) RFOR(i,0,(n))

int main() {
	int N;
	cin >> N;
	bool f = false;
	FOR(i,1,10) {
		FOR(j,1,10) {
			if(N == i*j) {
				f = true;
			}
		}
	}
	if(f) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}


Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
a.append(0)
m = 1000
s = 0

for i in range(n):
    if a[i] < a[i + 1]: #翌日上がるなら最大限買う
        sv = m//a[i]
        m -= a[i]*sv
        s += sv
    else:               #翌日同じか下がるなら全て売る
        m += a[i]*s
        s = 0

print(m)

Measured memory_bytes: 9096
#include<bits/stdc++.h>
#define add(a,b) a=(a+b)%mod
#define mod 1000000007
using namespace std;
int n, m, dp[3007][3007][2], res;
int main()
{
	cin >> n >> m;
	dp[0][0][1] = 1;
	for (int i = 1; i <= n; i++)
		dp[0][i][0] = 1;
	for (int i = 0; i < m; i++)
		for (int j = 0; j <= n; j++)
			for (int k = 0; k <= 1; k++)
			{
				if (j > 0)
					add(dp[i + 1][j - 1][k | (j - 1 == 0)], dp[i][j][k] % mod);
				if (j > 0)
					add(dp[i + 1][j][k | (j == 1)], dp[i][j][k] % mod);
				if (j < n)
					add(dp[i + 1][j][k], dp[i][j][k] % mod);
				if (j < n)
					add(dp[i + 1][j + 1][k], dp[i][j][k] % mod);
			}
	for (int i = 0; i <= n; i++)
		res = (res + dp[m][i][1]) % mod;
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 70784
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
#define D10 fixed<<setprecision(10)
typedef long long ll;
typedef long double ld;
typedef vector <ll> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1000000007;
const int INF = MOD + 1;
const ld EPS = 1e-12;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }

/*--------------------template--------------------*/

int main()
{
	cin.sync_with_stdio(false);
	int n, s, w, q;
	while (cin >> n >> s >> w >> q, n)
	{
		string a;
		int g = s;
		REP(i, n)
		{
			a += (g / 7) % 10 + '0';
			if (g % 2 == 0)  g = g / 2; 
			else g = (g / 2) ^ w; 
		}
		if (q == 2 || q == 5)
		{
			vi v(n); v[0] = (a[0] == '0' ? 0 : 1);
			FOR(i, 1, n) v[i] = v[i - 1] + (a[i] == '0' ? 0 : 1);
			int ans = 0;
			REP(i, n)
			{
				char t = a[i] - '0';
				if (t%q == 0) ans += v[i];
			}
			cout << ans << endl;
		}
		else
		{
			vi v(n + 1);
			ll t = 1;
			for (int i = n - 1; i >= 0; i--)
			{
				v[i] = (v[i + 1] + ((a[i] - '0') % q) * (t % q)) % q;
				t = t * 10 % q;
			}
			map<ll, int> mp;
			int ans = 0;
			for (int i = n; i >= 0; i--)
			{
				mp[v[i]]++;
				if (i == n || a[i] == '0') continue;
				ans += mp[v[i]] - 1;
			}
			cout << ans << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 9324
s = input()

s_list = ['T', 'C', 'G']

out = 0

for i in s_list:
  s = s.replace(i, 'A')

count = 0
for i in s:
  if i == 'A':
    count += 1
    if out < count:
      out = count
  else:
    count = 0

print(out)

Measured memory_bytes: 3060
import java.util.*;
public class Main{
    static Scanner sc = new Scanner(System.in);
    static long n = sc.nextLong();
    static int res = 0;
	public static void main(String[] args){
      dfs(0,false,false,false);
      System.out.println(res);
    }
    static void dfs(long num,boolean a,boolean b,boolean c){
    	if(num > n)return;
      if(a&&b&&c)res++;
      dfs(num*10+3,true,b,c);
      dfs(num*10+5,a,true,c);
      dfs(num*10+7,a,b,true);
    }
}


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

int main(){
  int a,b;
  cin >> a >> b;
  if(a*b == 2) cout << 3 << endl;
  else if(a*b == 3) cout << 2 << endl;
  else cout << 1 << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <string.h>
#include <cstdio>
#include <tuple>
using namespace std; using ll = long long; using pll = pair<ll, ll>;
using vl = vector<ll>; using vll = vector<vl>; using vpll = vector<pll>;
//**デバッグ準備**//
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
void debug_out() { cerr << endl; }
template<typename Head, typename... Tail>
void debug_out(Head h, Tail... t) {
	cerr << " " << h;
	if (sizeof...(t) > 0) cerr << " :";
	debug_out(t...);
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> vec) {
	for (size_t i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
	return os;
}
ll ctoi(char c) {
	switch (c) {
	case '0': return 0; case '1': return 1; case '2': return 2;
	case '3': return 3; case '4': return 4; case '5': return 5;
	case '6': return 6; case '7': return 7; case '8': return 8;
	case '9': return 9;  default: return 0;
	}
}
bool pairCompare(const pll firstElof, pll secondElof)
{
	return firstElof.first > secondElof.first;
}
//**Snippetリスト**//
//rep, vin, all, iteLoop//
//gcdlcm, isPrime, eratos, Npow, divisor, modinv, bitSearch, bitList, dfs, bfs//
//dijkstra, UnionFind, COM, digitDP//
ll i, j, k, l; ll N, M, K, H, W, L, X, Y, Z;
ll MOD = 1000000007; ll INF = 1LL << 60; ll ans = -INF; ll z = 0, o = 1;
vl flag, color, D; vector<vector<tuple<ll, ll, ll>>> path;
//***********//
int main() {
	cin >> N >> K;
	vector<vpll> G(K*2, vpll(K*2));
	for (i = 0; i < N; i++) {
		ll x, y; string c;
		cin >> x >> y >> c;
		x %= K*2; y %= K*2;
		if (c == "B") G[x][y].first++;
		else G[x][y].second++;
	}
	vll good(K*2, vl(K*2, 0));
	for (i = 0; i < K*2; i++) {
		vpll sum(K * 2 + 1);
		sum[0].first = 0; sum[0].second = 0;
		for (j = 0; j < K*2; j++) {
			sum[j + 1].first = sum[j].first + G[i][j].first;
			sum[j + 1].second = sum[j].second + G[i][j].second;
		}
		//Bスタートがj列目の時の適合数
		for (j = 0; j < K*2; j++) {
			if (j <= K) good[i][j] = sum[j].second + (sum[j+K].first - sum[j].first) + (sum[K * 2].second - sum[j + K].second);
			else good[i][j] = sum[(j + K) % (K * 2)].first + (sum[j].second - sum[(j + K) % (K * 2)].second) + (sum[K * 2].first - sum[j].first);
		}
		sum.clear();
	}
	//Bスタートがi列目の時のj行目までの累積和
	vll sum(K * 2, vl(K * 2 + 1));
	for (i = 0; i < K*2; i++) {
		sum[i][0] = 0;
	}
	for (i = 0; i < K*2; i++) {
		for (j = 0; j < K*2; j++) {
			sum[i][j + 1] = sum[i][j] + good[j][i];
			//debug(i, j + 1, good[j][i],sum[i][j + 1]);
		}
	}
	//デフォBスタートがi列目、反転スタートがj行目の時の適合数
	for (i = 0; i < K*2; i++) {
		for (j = 0; j < K*2; j++) {
			ll pre = 0;
			ll rev = (i + K) % (K * 2);
			if(j<=K) pre = sum[i][j] + (sum[rev][j + K] - sum[rev][j]) + (sum[i][K * 2] - sum[i][j + K]);
			else pre = sum[rev][(j + K) % (K * 2)] + (sum[i][j] - sum[i][(j + K) % (K * 2)]) + (sum[rev][K * 2] - sum[rev][j]);
			//debug(i, j, pre);
			ans = max(pre, ans);
		}
	}
	cout << ans;
}


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

int list[12];
int main(){
	int d;
	while(cin>>d&&d){
//		cout<<"-------- "<<d<<endl;
		for(int i=0;i<12;i++)list[i]=0;
		for(;d>0;d--){
			int n;
			cin>>n;
			list[n]++;
		}
		for(int i=0;i<10;i++){
	//		cout<<"["<<i<<"]";
			if(list[i]==0)cout<<"-";
			for(int j=0;j<list[i];j++){
				cout<<"*";
			}
			cout<<endl;
		}

	}

	return 0;
}

Measured memory_bytes: 0
import java.util.*;
import java.awt.*;
import static java.lang.System.*;
import static java.lang.Math.*;
//Loopで使う文字列の長さは固定！
//intで大丈夫？オーバーフローしない？
//Loop回数は本当に10⁹以内になってる？Loopは回る？？
public class Main {
    public static void main(String[]$){
        Scanner sc = new Scanner(in);
        int n=sc.nextInt();
        int[] a=new int[n+2];
        for (int i = 1; i <= n; i++) {
            a[i]=sc.nextInt();
        }
        int t=0;
        for (int i = 1; i <=1+n; i++) {
            t+=abs(a[i]-a[i-1]);
        }
        for (int i = 1; i <= n; i++) {
            int ans=0;
            if((a[i]-a[i-1])*(a[i+1]-a[i])>0)ans=t;
            if((a[i]-a[i-1])*(a[i+1]-a[i])<0)ans=t-abs(a[i]-a[i-1])-abs(a[i+1]-a[i])+abs(a[i+1]-a[i-1]);
            else ans=t;
            out.println(ans);
        }
    }
}

Measured memory_bytes: 63076
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int (i)=0;i<(n);i++)
#define REP(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define INF LLONG_MAX - 100
#define MOD 1000000007
#define fcout cout << fixed << setprecision(15)
#define int long long
#define yorn(f) puts((f)?"Yes":"No")
#define YORN(f) puts((f)?"YES":"NO")
#define second sec
#define first fir
typedef long long ll;
typedef pair<int, int> P;
typedef priority_queue<int> pque;
int gcd(int a,int b){return b?gcd(b,a%b):a;};
int lcm(int a,int b){return a/gcd(a,b)*b;};
int mod(int a,int b){return (a+b-1)/b;};
template<typename A, size_t N, typename T>
void Fill(A(&array)[N],const T &val){std::fill((T*)array,(T*)(array+N),val);}
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;};

const int N = 2005;
int u[N][N], d[N][N], l[N][N], r[N][N];
char s[N][N];

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

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            u[i][j] = 0;
            d[i][j] = 0;
            l[i][j] = 0;
            r[i][j] = 0;
            s[i][j] = '#';
        }
    }

    int H, W;
    cin >> H >> W;
    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W; ++j) {
            cin >> s[i][j];
        }
    }

    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W; j++) {
            if (s[i][j] != '#') {
                u[i][j] = u[i - 1][j] + 1;
                l[i][j] = l[i][j - 1] + 1;
            }
        }
    }

    for (int i = H; i >= 1; i--) {
        for (int j = W; j >= 1; j--) {
            if (s[i][j] != '#') {
                d[i][j] = d[i + 1][j] + 1;
                r[i][j] = r[i][j + 1] + 1;
            }
        }
    }

    int ans = 0;
    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W; j++) {
            if (s[i][j] != '#') {
                ans = max(ans, u[i][j] + d[i][j] + l[i][j] + r[i][j] - 3);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 129792
#include <iostream>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<math.h>
#include<bits/stdc++.h>
#include<cmath>
#include<iomanip>
using namespace std;

const double PI  =3.141592653589793238463;
#define pb push_back
#define pf push_front
#define sz(v)  ((int)(v).size());
#define all(v) ((v).begin()),((v).end())
typedef unsigned long long ull;
typedef long long ll;

typedef vector<int> vi;
typedef pair<int,int> pi;
//2 7 3 4 9

void printVec(vi v1)
{
    for(int i=0; i<v1.size(); i++)
        cout<<v1[i]<<" ";
    cout<<endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);


 ll n;cin>>n;
 map<ll,ll>MAP;
 ll new_n=sqrt(n);

for(ll x=1;x<=new_n;x++){
    for(ll y=1;y<=new_n;y++){
        for(ll z=1;z<=new_n;z++){
    ll v=(x*x)+(y*y)+(z*z)+(x*y)+(y*z)+(x*z);
    if(v>n){
        break;
    }
    MAP[v]++;

}
}
}

for(int i=1;i<=n;i++){
    cout<<MAP[i]<<endl;
}
    return 0;

}


Measured memory_bytes: 4116
#include<iostream>
#include<string>
#include<array>
using namespace std;

int main() {
	array<int,26> charList;
	string s;
	cin >> s;
	for (int i = 0; i < 26; ++i) {
		charList[i] = 0;
	}
	for (int i = 0; i < 4; i++) {

		charList[(int)s[i] - 64]++;
	}
	int count = 0;
	for (int i : charList) {
		if (i == 2) {
			count++;
		}
	}
	cout << (count == 2 ? "Yes" : "No") << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define debug cerr << "--" << __LINE__ << "--" << endl
typedef long long int ll;
using namespace std;
ll n, q, a, b, p, x;
vector<vector<ll> > adjList;
bool flg[200000];
vector<ll> ord;
ll since[200000], until[200000];

void dfs(ll from){
  ord.pb(from);
  flg[from] = true;
  since[from] = ord.size() - 1;
  for(auto adj : adjList[from]){
    if (!flg[adj]) dfs(adj);
  }
  until[from] = ord.size();
}

int main(){
  cin >> n >> q;
  adjList = vector<vector<ll> >(n);
  for(int i=0;i+1<n;i++){
    cin >> a >> b; a--; b--;
    adjList[a].pb(b);
    adjList[b].pb(a);
  }
  dfs(0);
  /*
  cerr << "ord: ";
  for(int i=0;i<ord.size();i++) cerr << ord[i] << " "; cerr << endl;
  cerr << "since: ";
  for(int i=0;i<n;i++) cerr << since[i] << " "; cerr << endl;
  cerr << "until: ";
  for(int i=0;i<n;i++) cerr << until[i] << " "; cerr << endl;
  */
  ll m = (ll) sqrt(n);
  vector<ll> cnt(n), cnt2(n);
  for(int i=0;i<q;i++){
    cin >> p >> x; p--;
    // add x[i] to [0, until[p])
    ll d = until[p]/m;
    for(int j=0;j<d;j++) cnt2[j] += x;
    for(int j=d*m;j<until[p];j++) cnt[j] += x;    
    // add -x[i] to [0, since[p])
    d = since[p]/m;
    for(int j=0;j<d;j++) cnt2[j] -= x;
    for(int j=d*m;j<since[p];j++) cnt[j] -= x;    
  }
  
  vector<ll> invord(n);
  for(int i=0;i<n;i++) invord[ord[i]] = i;
  
  
  for(int i=0;i<n;i++){
    int idx = invord[i];
    cout << cnt[idx] + cnt2[idx/m] << ((i+1<n) ? " " : "\n");
  }
  return 0;
}
  

Measured memory_bytes: 32372
#include<stdio.h>
#include<string.h>

#define M (1<<21)/* your task*/
#define L 14

char H[M][L]; /* Hash Table */

int getChar(char ch){
  if ( ch == 'A') return 1;
  else if ( ch == 'C') return 2;
  else if ( ch == 'G') return 3;
  else if ( ch == 'T') return 4;
  else return 0;
}

/* convert a string into an integer value */
long long getKey(char str[]){
  long long sum = 0, p = 1, i;
  for ( i = 0; i < strlen(str); i++ ){
    sum += p*(getChar(str[i]));
    p *= 5;
  }
  return sum;
}

int h1(int key){
  return key % 2;
}
int h2(int key){
  return 1 + (key % (M - 1));
}

int find(char str[]){
  long long key, i=0, h;
  key = getKey(str);
  for(i = 0;;i++){
    h = (h1(key) + i * h2(key)) % M;
    if(strcmp(H[h], str) == 0) return 1;
    else if(strlen(H[h]) == 0) return 0;
  }
  return 0;
}

int insert(char str[]){
  long long key, i, h;
  key = getKey(str);
  for(i = 0;;i++){
    h = (h1(key) + i * h2(key)) % M;
    if(strcmp(H[h], str) == 0) return 1;
    else if(strlen(H[h]) == 0){
      strcpy(H[h], str);
      return 0;
    }
  }
  return 0;
}

int main(){
    int i, n, h;
    char str[L], com[9];
    for ( i = 0; i < M; i++ ) H[i][0] = '\0';
    
    scanf("%d", &n);
    
    for ( i = 0; i < n; i++ ){
	scanf("%s %s", com, str);
	
	if ( com[0] == 'i' ){
	    insert(str);
	} else {
	    if (find(str)){
		printf("yes\n");
	    } else {
		printf("no\n");
	    }
	}
    }

    return 0;
}



Measured memory_bytes: 30408
N = int(input())
mod = 10**9+7

dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(N+1)]
dp[0][3][3][3] = 1
for i in range(N):
    for a in range(4):
        for b in range(4):
            for c in range(4):
                dp[i+1][0][a][b] = (dp[i+1][0][a][b] + dp[i][a][b][c]) % mod
                dp[i+1][3][a][b] = (dp[i+1][3][a][b] + dp[i][a][b][c]) % mod
                if a != 2 or b != 0:
                    dp[i+1][1][a][b] = (dp[i+1][1][a][b] + dp[i][a][b][c]) % mod
                if a == 1 and b == 0:
                    pass
                elif a == 0 and b == 1:
                    pass
                elif b == 1 and c == 0:
                    pass
                elif a == 1 and c == 0:
                    pass
                else:
                    dp[i+1][2][a][b] = (dp[i+1][2][a][b] + dp[i][a][b][c]) % mod

ans = 0
for a in range(4):
    for b in range(4):
        for c in range(4):
            ans = (ans + dp[-1][a][b][c]) % mod
print(ans)


Measured memory_bytes: 44400
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {

  while(1) {
    string s1, s2;
    cin >> s1;
    if(s1 == ".") return 0;

    cin >>s2;

    string s1_cp = s1, s2_cp = s2;

    vector<int> cnt1(s1.size()),cnt2(s1.size());

    int j = 0;
    for(int i = 0; i < s1.size(); i++) {
      if(s1[i] == '\"') {
        cnt1[j] = i;
        j++;
      }
    }

    int k = 0;
    for(int i = 0; i < s2.size(); i++) {
      if(s2[i] == '\"') {
        cnt2[k] = i;
        k++;
      }
    }

    // cout << "log1" << endl;

    int diff = 0;
    if(j == k) {
      vector<string> cut1(j);
      vector<string> cut2(j);
      int era_sum1 = 0, era_sum2 = 0;

      // cout << "j " << j << endl;
      for(int i = 0; i < j-1; i+=2) {

        cut1[i] = s1.substr(cnt1[i], (cnt1[i+1] - cnt1[i])+1);
        s1_cp.erase(s1_cp.begin()+cnt1[i]-era_sum1, s1_cp.begin()+cnt1[i+1]+1-era_sum1);
        s1_cp.insert(s1_cp.begin()+cnt1[i]-era_sum1, '*');
        era_sum1 += (cnt1[i+1] - cnt1[i]+1)-1;

        cut2[i] = s2.substr(cnt2[i], (cnt2[i+1] - cnt2[i])+1);
        s2_cp.erase(s2_cp.begin()+cnt2[i]-era_sum2, s2_cp.begin()+cnt2[i+1]+1-era_sum2);
        s2_cp.insert(s2_cp.begin()+cnt2[i]-era_sum2, '*');
        era_sum2 += (cnt2[i+1] - cnt2[i]+1)-1;

        // cout <<"cut[i]" << endl;
        // cout << cut1[i] << " " << cut2[i] << endl;
        // cout << s1_cp << " " << s2_cp << endl;
      }

      // cout << "log2" << endl;

      for(int i = 0; i < cut1.size(); i++) if(cut1[i] != cut2[i]) diff++;
    }

    if(s1 == s2) {
      cout << "IDENTICAL" << endl;
    }else if(diff == 1 && s1_cp == s2_cp) {
      cout << "CLOSE" << endl;
    } else {
      cout << "DIFFERENT" << endl;
    }
  }
  return 0;
}



Measured memory_bytes: 3212
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include <bitset>
#include<math.h>
#include<map>
#include<set>
using namespace std;
#define INF 11000000000
#define MOD 1000000007
typedef long long ll;
typedef pair<ll,ll> P;

int main(){
  int N,p,num[210000],count=1,ans=1;
  cin>>N;

  for(int i=0;i<N;i++){
    cin>>p;
    num[p]=i;
  }

  for(int i=1;i<N;i++){
    if(num[i+1]>num[i]) count++;
    else {
      count=1;
    }
    ans=max(ans,count);
  }
  cout<<N-ans<<endl;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
using p=pair<int,int>;
#define int long long
#define rep(i,N) for(int i=0;i<N;i++)

signed main(){
  int N;
  cin>>N;
  int ans=(24-N)+24;
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 3604
#include <stdio.h>
int main()
{
    int a, b;
    while (1)
    {
        scanf("%d %d", &a, &b);
        if (a == 0 && b == 0)
            break;
        else
        {
            if (a > b)
                printf("%d %d\n", b, a);
            else
                printf("%d %d\n", a, b);
        }
    }
    return 0;
}


Measured memory_bytes: 2060
#include <stdio.h>

int main()
{
	int C[9];
	for(int i = 0; i < 9; i++)
		scanf("%d", &C[i]);
	
	int p1 = C[0]+C[4]+C[8];
	int p2 = C[1]+C[5]+C[6];
	int p3 = C[2]+C[3]+C[7];
	
	printf(p1==p2 && p2==p3 ? "Yes" : "No") ;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
//string s[3]={"Sunny","Cloudy","Rainy"} ;
int main()
{
	string a;
	while (cin>>a)
	{
		if (a=="Sunny")
			cout<<"Cloudy"<<endl;
		else if (a=="Cloudy")
			cout<<"Rainy"<<endl;
		else cout<<"Sunny"<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main() {
	int data[10] = {0};
	int i, j, temp;
	for(i = 0; i < 10; i++) {
		scanf("%d", &data[i]);
	}
	for(i = 0; i < 9; i++) {
		for(j = 9; j > i; j--) {
			if(data[j-1] > data[j]) {
				temp = data[j];
				data[j] = data[j-1];
				data[j-1] = temp;
			}
		}
	}
	printf("%d\n%d\n%d\n", data[9], data[8], data[7]);
	return 0;
}

Measured memory_bytes: 600