akhauriyash/Code-Regression huggingface dataset:
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <iostream>
#include <fstream>

#include<bits/stdc++.h>
using namespace std;

#define rep(i,n) for(int64_t i = 0;i < n;i++)

template<class T> bool chmin(T& a,T b){
    if(a > b){ a = b; return true; }else return false;
}
template<class T> bool chmax(T& a,T b){
    if(a < b){ a = b; return true; }else return false;
}
using ll = int64_t;
/*
 * Modint struct
 * library author : @snuke
 * */
const int mod = 1e9 + 7;
struct mint {
  long long x; // typedef long long ll;
  mint(long long x=0):x((x%mod+mod)%mod){}
  mint& operator+=(const mint a) { if((x+=a.x)>=mod)x-=mod;return *this;}
  mint& operator-=(const mint a) { if((x+=mod-a.x)>=mod)x-=mod; return *this;}
  mint& operator*=(const mint a) { (x *=a.x)%=mod; return *this;}
  mint operator+(const mint a) const { mint res(*this);return res+=a;}
  mint operator-(const mint a) const { mint res(*this);return res-=a;}
  mint operator*(const mint a) const { mint res(*this);return res*=a;}
  mint pow(ll t) const {
    if (!t) return 1;mint a = pow(t>>1);a*=a;
    if (t&1) a *= *this;return a;
  }
  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return (*this) *= a.inv();}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
class HGrid1 {
public:
	void solve(std::istream& cin, std::ostream& cout) {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);

        int64_t h,w;cin >> h >> w;
        vector<string> g(h);
        rep(i,h)cin >> g[i];

        vector<vector<mint>> dp(h,vector<mint>(w,0));
        dp[0][0] = 1;
        rep(i,h)rep(j,w){
            if(i+1 < h && g[i+1][j] == '.') dp[i+1][j] += dp[i][j];
            if(j+1 < w && g[i][j+1] == '.') dp[i][j+1] += dp[i][j];
        }
        cout << dp[h-1][w-1] << '\n';
        //int t;cin >> t;rep(i,t)main2(cin,cout);
	}
	void main2(istream& cin,ostream& cout){

	}
};


int main() {
	HGrid1 solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 9216
using System;

namespace ABC108_A_Pair
{
	internal class Program
	{
		public static void Main(string[] args)
		{
			int k = int.Parse(Console.ReadLine());
			int count = 0;

			for (int i = 1; i < k; i++)
			{
				for (int j = i + 1; j <= k; j++) {
					if (i % 2 == 0 && j % 2 == 1)
					{
						count++;
					}else if (i % 2 == 1 && j % 2 == 0)
					{
						count++;
					}
				}
			}
			
			Console.WriteLine(count);
		}
	}
}

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

int main(){
  string S; cin >> S;
  int MAX = 0;
  int count = 0;
  for(int i=0;i<S.size();i++){
    if(S.at(i) == 'A' || S.at(i) == 'C' || S.at(i) == 'G' || S.at(i) == 'T' ){
      count++;
      if(MAX < count) MAX = count;
    }else{
      count = 0;
    }
  }
  cout << MAX << endl;
}


Measured memory_bytes: 3616
#include <iostream>
#include <cstdint>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cassert>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <unordered_set>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpii;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvc;
typedef vector<vector<string>> vvs;
typedef vector<vector<ll>> vvll;

#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rrep(i, n) for (ll i = 1; i <= (n); ++i)
#define irep(it, stl) for (auto it = stl.begin(); it != stl.end(); it++)
#define drep(i, n) for (ll i = (n)-1; i >= 0; --i)
#define mes(a) cout << (a) << endl
#define dmes(a, b) cout << (a) << " " << (b) << endl
#define re0 return 0
#define mp(p, q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define rSort(a) sort(a.rbegin(), a.rend())
#define Rev(a) reverse(a.begin(), a.end())
#define popcnt(n) __builtin_popcount(n)
#define MATHPI acos(-1)
#define itn int
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return 1;
    }
    return 0;
}
struct io
{
    io()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
    }
};
const int INF = INT_MAX;
const ll LLINF = 1LL << 60;
const ll MOD = 1000000007;
const double EPS = 1e-19;


const int NMAX=1000001;


signed main() {
    string s;
    cin >> s;
    
    ll l = (ll)s.size();
    
    if (s[l-1] == 's') {
        cout << s << "es";
    } else {
    cout << s << "s";
    }
    
 
    
}

Measured memory_bytes: 3616
N,M,K = list(map(int, input().split()))
mod = 10**9 + 7

tn = 0
tm = 0
for n in range(N):
  tn = (tn + n*(n+1)//2)%mod
tn = tn*M*M %mod
for m in range(M):
  tm = (tm + m*(m+1)//2)%mod
tm = tm*N*N %mod

#N*M C K-2
class combinationmod():
  def __init__(self,MAX, mod):
    self.mod =mod
    self.fac=[0]*(MAX+1)
    self.finv=[0]*(MAX+1)
    self.inv=[0]*(MAX+1)
    self.fac[0]=self.fac[1]=1
    self.finv[0]=self.finv[1]=1
    self.inv[1]=1
    for i in range(2,MAX+1):
      self.fac[i] = self.fac[i-1]*i%mod
      self.inv[i] = (-self.inv[mod%i]*(mod//i))%mod
      self.finv[i] = self.finv[i-1]* self.inv[i] %mod

  def nCk(self,n,k):
    if n<k or n<0 or k<0:
      return 0
    return self.fac[n]*(self.finv[k]*self.finv[n-k]%self.mod)%self.mod

c = combinationmod(200000,int(1e9+7))


ans = (tn + tm)*c.nCk(N*M-2, K-2) %mod
print(ans)

Measured memory_bytes: 26868
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
int main(){
	string s;
	int len,ans=0;
	cin>>s;
	len=s.length();
	int mid;
	mid=len/2-1;
	for(int i=0;i<=mid;i++){
		if(s[i]!=s[len-i-1]) ans++;
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 256
<?php
  $s = trim(fgets(STDIN));
  $flag = true;
  for($i=0; $i<strlen($s); $i++){
      if($i%2==0){
          if($s[$i] == "L") $flag = false;
      } else {
          if($s[$i] == "R") $flag = false;
      }
  }
  if($flag){
      echo "Yes";
  }else{
      echo "No";
  }

Measured memory_bytes: 4732
def main():
    H, W = map(int, input().split())
    A = [0]*H
    for i in range(H):
       A[i] = [a for a in input()]
    # print(A)
    B = []
    for i in range(H):
        found = False
        for j in range(W):
            if A[i][j] == '#':
                found = True
                break
        if found:
            B.append(A[i])
    # print(B)
    h = len(B)
    C = [[] for i in range(h)]
    for j in range(W):
        found = False
        for i in range(h):
            if B[i][j] == '#':
                found = True
                break
        if found:
            for i in range(h):
                C[i].append(B[i][j])
    for i in range(h):
        print(''.join(C[i]))


if __name__ == '__main__':
    main()


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

#define rep(i,n) for(int i = 0; i < n; i++)
#define REP(i,n) for(int i = 1; i < n; i++)
#define sz(x) int(x.size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define endl '\n'
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
using vi = vector<int>;
using vii = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;
using vs = vector<string>;
using vb = vector<bool>;
using vc = vector<char>;
using vcc = vector<vc>;
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
const int inf = (1<<30)-1;
const ll infll = (1LL<<62)-1;
ll ceil(const ll &a, const ll &b){return ((a)+(b)-1)/b;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }



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

  int a, b, c, d, e, f;
  cin >> a >> b >> c>> d >> e >> f;
  set<int> suger, water;
  rep(i,f+1) {
    rep(j,f+1) {
      int x = a*100*i + b*100*j;
      if(x <= f) water.insert(x);
      int y = c*i + d*j;
      if(y <= f) suger.insert(y);
    }
  }
  double con = 0;
  P ans = make_pair(100*a,0);
  for(auto i = water.begin(); i != water.end(); i++) {
    for(auto j = suger.begin(); j != suger.end(); j++) {
      int x = *i;
      int y = *j;
      if(x+y > f) continue;
      if(y == 0) continue;
      if(x/100*e < y) continue;
      double tmp = (double)100*y / (double)(x+y);
      if(tmp > con) {
        ans = make_pair(x+y, y);
        con = tmp;
      }
    }
  }
  cout << ans.first << ' ' << ans.second << endl;
}

Measured memory_bytes: 384
local List = {}
function List.new ()
    return {first = 0, last = -1}
end

function List.pushleft (list, value)
    local first = list.first - 1
    list.first = first
    list[first] = value
end

function List.pushright (list, value)
    local last = list.last + 1
    list.last = last
    list[last] = value
end

function List.popleft (list)
    local first = list.first
    local value = list[first]
    list[first] = nil
    list.first = first + 1
    return value
end

function List.popright (list)
    local last = list.last
    local value = list[last]
    list[last] = nil
    list.last = last - 1
    return value
end

function List.empty (list)
    return list.first > list.last
end

----------

local n=io.read("n")
local graph={}
for i=1,n do
    graph[i]={}
end
for i=1,n-1 do
    local a,b=io.read("n","n")
    graph[a][b]=i
    graph[b][a]=i
end

local que=List.new()
List.pushright(que,1)
local out={}
local k=0
while not List.empty(que) do
    local a=List.popleft(que)
    local used=0
    for b,i in pairs(graph[a]) do
        if out[-i] then
            used=used+out[-i]
            break
        end
    end
    local deg=0
    local color=1
    for b,i in pairs(graph[a]) do
        if color==used then
            color=color+1
        end
        out[i]=color
        if graph[a][b]>0 then
            graph[a][b]=-graph[a][b]
            graph[b][a]=-graph[b][a]
            List.pushright(que,b)
            color=color+1
        end
        deg=deg+1
    end
    k=math.max(deg,k)
end

print(k)
for i=1,n-1 do
    print(out[i])
end

Measured memory_bytes: 28392
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int k = sc.nextInt();
		String s = sc.next();

		if(s.length() <= k) {
			System.out.println(s);
		}else {
			for(int i=0 ; i<k ; i++) {
				System.out.print(s.charAt(i));
			}
			System.out.println("...");
		}

		sc.close();




	}
}


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

int main()
{
  int N; ll K; cin >> N >> K;
  vector<int> A;
  map<int, ll> AM;
  for (int i = 0; i < N; i++) {
    int a, b; cin >> a >> b;
    if (AM[a] == 0) {
      A.push_back(a);
      AM[a] = b;
    } else {
      AM[a] += b;
    }
  }
  sort(A.begin(), A.end());
  int ans;
  ll k = 0;
  for (int a : A) {
    k += AM[a];
    if (K <= k) {
      ans = a;
      break;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 4476
#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define N 501000
using namespace std;
int a[N],b[N],f[N],n,m;
int main()
{
	scanf("%d%d",&n,&b[0]);
	fo(i,1,n) scanf("%d",&a[i]),b[i]=min(b[i-1],abs(b[i-1]-a[i]));
	f[n+1]=1;
	fd(i,n,1) if((a[i]/2)>=f[i+1]) f[i]=f[i+1];else f[i]=f[i+1]+a[i];
	scanf("%d",&m);
	while(m--)
	{
		int x;scanf("%d",&x);
		if(b[x-1]<f[x+1]) printf("NO\n");
		else printf("YES\n");
	}
}

Measured memory_bytes: 7680
h, w = [int(x) for x in input().split()]
a = [ [int(x)%2!=0 for x in input().split()] for _ in range(h)]

mvs = []
for i, row in enumerate(a):
    if i<h-1:
        for j, elem in enumerate(row):
            if elem:
                mvs.append((i, j, i+1, j))
                a[i+1][j] = not a[i+1][j]
    else:
        for j, elem in enumerate(row):
            if j==w-1:
                break
            if elem:
                mvs.append((i, j, i, j+1))
                a[i][j+1] = not a[i][j+1]

print(len(mvs))
for y, x, yp, xp in mvs:
    print(y+1, x+1, yp+1, xp+1)

Measured memory_bytes: 22656
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
using ll = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b)a=b;};
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b)a=b;};

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

  Int t,d;
  Int ta,tb,da,db;
  cin>>t>>d>>ta>>tb>>da>>db;

  using D = double;
  D ans=1e18;
  for(Int i=0;i<=d;i++){
    for(Int j=0;j<=d;j++){
      Int v=i*da+j*db;
      if(v==0||v>d) continue;
      Int sm=ta*(i*da)+tb*(j*db);
      chmin(ans,abs(t-(D)sm/v));
    }
  }
  
  cout<<fixed<<setprecision(12)<<ans<<endl;
  return 0;
}



Measured memory_bytes: 3300
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int X = sc.nextInt();
    int t = 1;
    while (true) {
      if (X <= t * (t + 1) / 2) {
        System.out.println(t);
        return;
      }
      t++;
    } 
  }
}

Measured memory_bytes: 22996
/*
 *        ~Botay~
 *    code by kazalika
 */

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ldb;
typedef double db;
typedef vector<int> vint;
typedef vector<ll> vll;
#define forn(a, i, n) for (int i = (a); i < (n); ++i)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) int(x.size())
const int N = 3e6 + 6;



int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.precision(20);

  int n;
  cin >> n;
  vll a(n);
  forn(0, i, n) cin >> a[i];
  sort(all(a));
  if (!a[0]) {
    cout << 0;
    return 0;
  }
  ll rs = 1;
  forn(0, i, n) {
    if ((ll)1e18 / a[i] < rs) {
      cout << -1;
      return 0;
    }
    rs *= a[i];
  }
  if (rs > (ll)1e18) cout << -1;
  else cout << rs;

}

Measured memory_bytes: 3952
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string>
#include<math.h>
#include<vector>
#include<iomanip>
using namespace std;

int main(void)
{
	int counter = 0;
	string s;
	cin >> s;
	int count[1000];
	for (int i = 0; i < 1000; i++) { count[i] = 0; }
	for (int i = 0; i < 4; i++) { count[s[i]] += 1; }
	for(int i = 0;i < 1000;i++)
	{
		if (count[i] == 2) { counter++; }
	}
	if (counter == 2) { cout << "Yes" << endl; }
	else { cout << "No" << endl; }
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define repd(i, n) for (ll i = (ll)(n)-1; i >= 0; i--)
const ll INF = 1LL << 60;
const int INF32 = 1 << 29;
const ll MOD = 1000000007;
using Graph = vector<vector<int>>; // グラフ型

int main()
{
    string S;
    cin >> S;
    int N;
    N = S.length();
    string rS = S;
    rep(i, N)
    {
        rS[i] = S[N - 1 - i];
    }
    if (S != rS)
    {
        cout << "No" << endl;
        return 0;
    }

    string fS = "";
    string lS = "";

    rep(i, (N - 1) / 2)
    {
        fS += S[i];
    }

    rep2(i, (N + 3) / 2 - 1, N)
    {
        lS += S[i];
    }

    string rfS = fS;
    rep(i, fS.length())
    {
        rfS[i] = fS[fS.length() - 1 - i];
    }
    if (fS != rfS)
    {
        cout << "No" << endl;
        // rep(i, fS.length())
        // {
        //     cout << fS[i];
        // }
        // cout << endl;
        return 0;
    }

    string rlS = lS;
    rep(i, lS.length())
    {
        rlS[i] = lS[lS.length() - 1 - i];
    }
    if (lS != rlS)
    {
        cout << "No" << endl;

        // rep(i, lS.length())
        // {
        //     cout << lS[i];
        // }
        // cout << endl;
        return 0;
        // cout << 2;
    }

    cout << "Yes" << endl;
}

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

long long cube(int x) {
    return 1ll * x * x * x;
}

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

    if (k % 2 == 1) {
        cout << cube(n / k) << endl;
    } else {
        cout << cube(n / k) + cube((n + k / 2) / k) << endl;
    }
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskX solver = new TaskX();
		solver.solve(1, in, out);
		out.close();
	}

	static int INF = 1 << 30;
	static int modP = 1000000007;
	static int[] mh4 = { 0, -1, 1, 0 };
	static int[] mw4 = { -1, 0, 0, 1 };

	static class TaskX {
		public void solve(int testNumber, InputReader in, PrintWriter out) {

			int n = in.nextInt();
			int gc = 0, kc = 0;
			long[] a = new long[n];
			for (int i = 0; i < n; i++) {
				long t = in.nextLong();
				if (t % 2 == 0) {
					gc++;
				} else {
					kc++;
				}
				a[i] = t;
			}

			if (kc % 2 == 0) {
				out.println("YES");
			} else {
				out.println("NO");
			}

		}
	}

	static class InputReader {
		BufferedReader in;
		StringTokenizer tok;

		public String nextString() {
			while (!tok.hasMoreTokens()) {
				try {
					tok = new StringTokenizer(in.readLine(), " ");
				} catch (IOException e) {
					throw new InputMismatchException();
				}
			}
			return tok.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(nextString());
		}

		public long nextLong() {
			return Long.parseLong(nextString());
		}

		public double nextDouble() {
			return Double.parseDouble(nextString());
		}

		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextInt();
			}
			return res;
		}

		public long[] nextLongArray(int n) {
			long[] res = new long[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextLong();
			}
			return res;
		}

		public InputReader(InputStream inputStream) {
			in = new BufferedReader(new InputStreamReader(inputStream));
			tok = new StringTokenizer("");
		}

	}

}


Measured memory_bytes: 36296
#include<iostream>
#include<unordered_set>
#include<string>
int main(){
    int n;
    std::string tmp,a="MARCH";
    std::unordered_set<std::string> s[5];
    std::cin >> n;
    for(int i=0;i<n;i++){
        std::cin >> tmp;
        for(int j=0;j<5;j++){
            if(tmp[0]==a[j]){
                s[j].emplace(tmp);
                break;
            }
        }
    }
    long long cnt[5],sum=0;
    for(int i=0;i<5;i++)cnt[i]=(long long)s[i].size();
    for(int i=0;i<5;i++){
        for(int j=i+1;j<5;j++){
            for(int k=j+1;k<5;k++){
                sum+=cnt[i]*cnt[j]*cnt[k];
            }
        }
    }
    std::cout << sum;
    return 0;
}

Measured memory_bytes: 9216
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# (X - Y) (X^4 + X^3 Y + X^2 Y^2 + X Y^3 + Y^4)
X = ir()

def make_divisors(n):  # nの約数を列挙
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

U = 10 ** 4
div = make_divisors(X)
for a in range(U):
    for d in div:       
        b = a - d
        if a ** 5 - b ** 5 == X:
            print(a, b)
            exit()


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

using namespace std;

#define LL long long
#define DD double
#define Pb push_back
#define Bp pop_back
#define Pf push_front
#define Fp pop_front
#define Ub upper_bound
#define Lb lower_bound
#define In insert
#define All(x) x.begin(), x.end()
#define mem(a, b) memset(a, b, sizeof(a))
#define fast ios_base::sync_with_stdio(0);cin.tie(0)
#define X first
#define Y second
#define mx1 10
#define mx2 110
#define mx3 1010
#define mx4 10010
#define mx5 100010
#define mx6 1000010

typedef vector<LL> Vl;
typedef vector<DD> Vd;
typedef vector<bool> Vb;
typedef vector<Vl> VVl;
typedef pair<LL, LL> Pll;
typedef pair<DD, DD> Pdd;
typedef vector<Pll> Vpl;
typedef vector<Pdd> Vpd;
typedef queue<LL> Ql;
typedef stack<LL> Sl;
typedef deque<LL> Dl;

LL _set(LL N, LL pos) {return N = N | (1 << pos);}
LL _reset(LL N, LL pos) {return N = N & ~(1 << pos);}
bool _check(LL N, LL pos) {return (bool)(N & (1 << pos));}
bool _upper(char a) {return a >= 'A' && a <= 'Z';}
bool _lower(char a) {return a >= 'a' && a <= 'z';}
bool _digit(char a) {return a >= '0' && a <= '9';}

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

///**************************DONE****************************///

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

    int x = (n + 1) / 2;
    cout << fixed << setprecision(12) << (DD)x / (DD)n << '\n';
    return 0;
}


Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
cntL = 0
s = sum(a) // 2
cntR = 0
for i in range(len(a)):
    if cntL + a[i] < s:
        cntL += a[i]
    else:
        cntR = cntL
        cntL += a[i]
        break
# print(cntL)
print(min(abs((sum(a) - cntL) - cntL),abs(sum(a) - cntR) - cntR))
# print(abs(sum(a) - cntR) - cntR)


Measured memory_bytes: 26396
import java.io.*;
import java.util.*;
import java.util.function.*;

final class Solver {
	static final Solver INSTANCE = new Solver();

	void solve(Supplier<String> sc) {
		for (int i = 0; i < 5; i++) {
			int x = Integer.parseInt(sc.get());
			if (x == 0) {
				System.out.println(i + 1);
				return;
			}
		}
	}
}

class Main {
	public static void main(String... args) {
		System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
		var reader = new BufferedReader(new InputStreamReader(System.in));
		Solver.INSTANCE.solve(new Supplier<>() {
			StringTokenizer line;

			public String get() {
				while (line == null || !line.hasMoreTokens()) try {
					line = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new UncheckedIOException(e);
				}
				return line.nextToken();
			}
		});
		System.out.flush();
	}
}

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

H,W=map(int,input().split())
a = [list(map(int, input().split())) for _ in range(H)]

for i in range(H):
    if i%2==1:
        a[i].reverse()

ans=[]
for x in range(H):
    for y in range(W):
        if x%2==0 and a[x][y]%2==1:
            if y!=W-1:
                ans.append([x,y,x,y+1])
                a[x][y+1] += 1
            elif x<H-1:
                ans.append([x,y,x+1,y])
                a[x+1][0] += 1
        elif x%2==1 and a[x][y]%2==1:
            if y!=W-1:
                ans.append([x,W-1-y,x,W-1-y-1])
                a[x][y+1] += 1
            elif x<H-1:
                ans.append([x,W-1-y,x+1,W-1-y])
                a[x+1][0] += 1
print(len(ans))
for i in range(len(ans)):
    for j in range(4):
        ans[i][j]+=1
    print(*ans[i])



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

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

typedef long long ll;
using namespace std;
int mod = 1000000007;

int main(void){
    int N; cin >> N;
    int i = 1;
    int acc = 0;
    for(; acc < N; i++) acc += i;
    int no_out = acc - N;
    for(int j = 1; j < i; j++){
        if(j == no_out) continue;
        else cout << j << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
#define INF 0x3f3f3f3f
static const int MAXN=10000;
int vis[MAXN+10],d[MAXN+10];
int n;
vector<pair<int,int> >adj[MAXN];
void dijkstra()
{
    priority_queue<pair<int,int> > PQ;
    memset(d,0x3f,sizeof(d));
    memset(vis,0,sizeof(vis));
    d[0]=0;
    PQ.push(make_pair(0,0));
    vis[0]=1;
    while(!PQ.empty())
    {
        pair<int,int> f=PQ.top();
        PQ.pop();
        int u=f.second;
        vis[u]=2;
        if(d[u]<f.first*(-1))
            continue;
        for(int j=0;j<adj[u].size();j++)
        {
            int v=adj[u][j].first;
            if(vis[v]==2)
                continue;
            if(d[v]>d[u]+adj[u][j].second)
            {
                d[v]=d[u]+adj[u][j].second;
                PQ.push(make_pair(d[v]*(-1),v));
                vis[v]=1;
            }
        }
    }
    for(int i=0;i<n;i++)
        cout<<i<<" "<<(d[i]==INF?-1:d[i])<<endl;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0),cout.tie(0);
    int u,k,v,c;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>u>>k;
        for(int j=0;j<k;j++)
        {
            cin>>v>>c;
            adj[u].push_back(make_pair(v,c));
        }
    }
    dijkstra();
    return 0;
}


Measured memory_bytes: 8280
import java.util.*;
import java.lang.*;
import java.io.*;
class Main
{
	public static void main (String[] args) throws IOException
	{
			BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		    int n=Integer.parseInt(br.readLine());
		    String st[]=br.readLine().trim().split(" ");
		    int a[]=new int[n];
		    int dp[]=new int[n];
		    int i;
      //System.out.println("hello");
		    for(i=0;i<n;i++){
		        a[i]=Integer.parseInt(st[i]);
		    }
		    dp[0]=0;
		    dp[1]=Math.abs(a[1]-a[0]);
		    for(i=2;i<n;i++){
		        dp[i]=Math.min(dp[i-1]+Math.abs(a[i]-a[i-1]),dp[i-2]+Math.abs(a[i]-a[i-2]));
		    }
		    System.out.println(dp[n-1]);
	}
}

Measured memory_bytes: 33916
def gcd(a, b):
    if a > b:
        a,b = b,a
    if a == 0:
        return b
    else:
	    while b:
		    a, b = b, a % b
	    return a

n = int(input())
a = list(map(int,input().split()))
l = [0]
r = [0]
for i in range(n):
    l.append(gcd(l[i],a[i]))
for i in range(n):
    r.append(gcd(r[i],a[-i-1]))
r.reverse()
ans = 0
for i in range(n):
    if ans < gcd(l[i],r[i+1]):
        ans = gcd(l[i],r[i+1])
print(ans)


Measured memory_bytes: 14524
def main():
    N = int(input())
    distance = [-1 for _ in range(N)]
    edges = [[] for _ in range(N)]
    nodes = [0]
    for _ in range(N-1):
        u, v, w = map(int, input().split())
        edges[u-1].append((v-1, w))
        edges[v-1].append((u-1, w))
    distance[0] = 0
    while any(d < 0 for d in distance):
        n = nodes.pop(0)
        for edge in edges[n]:
            m, d = edge[0], edge[1]
            if distance[m] == -1:
                distance[m] = distance[n] + d
                nodes.append(m)
    for d in distance:
        print(0 if d % 2 == 0 else 1)


if __name__ == '__main__':
    main()


Measured memory_bytes: 42796
#include<bits/stdc++.h>
#define FOR(i,a,b) for(long long i = (long long)(a); i < (long long)(b); i++)
#define RFOR(i,a,b) for(long long i = (long long)(a); i >= (long long)(b); i--)
#define MIN3(a,b,c) (a)<(b)?((a)<(c)?(a):(c)):((b)<(c)?(b):(c))
#define MAX(a,b) (a)>(b)?(a):(b)
#define MIN2(a,b) (a)<(b)?(a):(b)
using namespace std;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef long long ll;
#define ull unsigned long long
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll,ll> lll;
#define deb(x )     cerr << #x << " here "<< x << endl;
#define endl    "\n"
#define printCase() "Case #" << caseNum << ": "
inline bool is_palindrome(const string& s){ return std::equal(s.begin(), s.end(), s.rbegin()); }
const ll MOD = 1000000007;
const ll INF = 1e9+5;
const double eps = 1e-7;
const double PI = acos(-1.0);
#define coud(a,d) cout << fixed << showpoint << setprecision(d) << a;
inline void debug_vi(vi a) {FOR(i, 0, a.size()) cout<<a[i]<<" ";}
inline void debug_vll(vll a) {FOR(i, 0, a.size()) cout<<a[i]<<" ";}
#define ff first
#define ss second
/*----------------------------------------------------------------------*/

const int N = 3005;
ll dp[N][N], pref[N];

int main(){
    std::ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);
    int n; cin>>n; string s; cin>>s;
    memset(dp, 0, sizeof(dp));
    dp[1][1] = 1;
    FOR(i, 2, n + 1) {
    	memset(pref, 0, sizeof(pref));
    	FOR(j, 1, n+1) {
    		pref[j] = (pref[j - 1] + dp[i-1][j])%MOD;
    	}
    	FOR(j, 1, i+1) {
    		int lo, hi;
    		if (s[i-2] == '<')
    		{
				lo = 1;
				hi = j-1;
    		} else {
    			lo = j;
    			hi = n - 1;
    		}
    		if (lo <= hi)
    		{
    			dp[i][j] += (pref[hi] - pref[lo-1] + MOD)%MOD;
    			dp[i][j] %= MOD;	
    		}
    	}
    }
    ll ans = 0;
    FOR(i, 1, n+1) {
    	ans += dp[n][i];
    	ans %= MOD;
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 70784
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define setbits(x) __builtin_popcount(x)
#define setbitsll(x) __builtin_popcountll(x)
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define se second
#define fi first
#define pai acos(-1)
#define fn(i,x) for(i=0;i<x;i++)
#define fs(i,s,x) for(i=s;i<x;i++)
#define fr(i,x,s) for(i=x;i>=s;i--)
#define fit(itr,s) for(itr=s.begin();itr!=s.end();itr++)
#define W while
#define pp pair<ll,ll>
#define ppi pair<int,int>
#define vl vector<ll>
#define vll vector<pp >
#define vi vector<int>
#define vii vector<ppi>
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define debug(x) cerr<<#x<<" :: "<<x<<endl;
#define debug2(x,y) cerr<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<endl;
#define debug3(x,y,z) cerr<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<endl;
#define debug4(x,y,z,w) cerr<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<"\t"<<#w<<" :: "<<w<<endl;
#define boost  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
const ll MAX=1e16;
const ll MM=1e18;
const ll mod=998244353;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};

ll expo(ll x,ll n,ll M=mod)
{
    ll ans=1;
    while(n>0)
    {
        if(n&1){ans=(ans*x)%M;}
                x=(x*x)%M;
                n>>=1;
    }
    return ans;
}
const ll MaxSize = 3e5;
ll facts[MaxSize], invFacts[MaxSize];

void preproc() {
  facts[0] = 1;
  for (int i = 1; i < MaxSize; i++) {
    facts[i] = ((ll)facts[i - 1] * i) % mod;
  }
  invFacts[MaxSize - 1] = expo(facts[MaxSize - 1], mod - 2,mod);

  for (int i = MaxSize - 2; i >= 0; i--) {
    invFacts[i] = ((ll)invFacts[i + 1] * (i + 1)) % mod;
  }
}

ll combination(ll n, ll k) {
  if(n<k) return 0;
  ll res = facts[n];
  res = ((ll)res * invFacts[k]) % mod;
  return ((ll)res * invFacts[n - k]) % mod;
}

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



void solve()
{
    
    int n;
    cin >> n;
    map<int, int> mp;
    for(int i = 0; i < n-1; i++) {
        int a;
        cin >> a;
        mp[a]++;
    }
    for(int i = 1; i <= n; i++) {
        cout << mp[i] << endl;
    }
} 
int main()
{
  boost;
  int m;
  //cin >> m;
  int t=1;
  //cin>>t;
  while(t--)
  {
      solve();
  }
}



Measured memory_bytes: 12984
#include<algorithm>
#include<bitset>
#include<climits>
#include<cmath>
#include<cstdlib>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<string>
#include<time.h>
#include<tuple>
#include<utility>
#include<vector>

using namespace std;
const long mod = 1000000007;
long gcd(long x, long y) { if (x > y) { return gcd(y, x); } long r; while (y != 0) { r = x % y; x = y; y = r; }return x; }
long lcm(long x, long y) { return(x / gcd(x, y)) * y; }

int main() {

	string s, t; cin >> s >> t;
	long slen = s.length();
	long tlen = t.length();
	//sに出てくる文字の集合
	set<char> ins;
	for (int i = 0; i < slen; i++) ins.insert(s[i]);
	//tがsの部分列として含まれるかどうかの判定
	for (int i = 0; i < tlen; i++) if (ins.find(t[i]) == ins.end()) { cout << -1 << endl; return 0; }
	//ssに文字chが何文字目に現れるか
	string ss = s + s;
	vector<vector<long>> ch(26); //ch[0]はaの位置、ch[25]はzの位置
	for (int i = 0; i < slen * 2 - 1; i++) ch[(long)(ss[i] - ('a'))].push_back(i + 1);

	long res = 0;

	//chのなかでmodres以上のupper_bound
	long next;
	for (int i = 0; i < tlen; i++) {
		next = *upper_bound(ch[t[i] - 'a'].begin(), ch[t[i] - 'a'].end(), res % slen);
        res += (next - res % slen) ;
	}
	cout << res << endl;
}

Measured memory_bytes: 3000
#include<stdio.h>
#define MAX 100000
#define SENTINEL 1000000000

struct Card{
  char suit;
  int value;};
struct Card L[MAX/2+2],R[MAX/2+2];

void merge(struct Card A[], int n, int left, int mid, int right){
  int i,j,k;
  int n1=mid-left;
  int n2=right-mid;
  for(i=0;i<n1;i++)L[i]=A[left+i];
  for(i=0;i<n2;i++)R[i]=A[mid+i];
  R[n2].value=SENTINEL;
  L[n1].value=R[n2].value;
  j=0;
  i=j;
  for(k=left;k<right;k++){
    if(L[i].value<=R[j].value)A[k]=L[i++];
    else A[k]=R[j++];
  }
}

void mergeSort(struct Card A[], int n, int left, int right){
  int mid;
  if(left+1<right){
    mid=(left+right)/2;
    mergeSort(A,n,left,mid);
    mergeSort(A,n,mid,right);
    merge(A,n,left,mid,right);
  }
}

int partition(struct Card A[], int n, int p, int r){
  int i,j;
  struct Card t,x;
  x=A[r];
  i=p-1;
  for(j=p;j<r;j++){
    if(A[j].value<=x.value){
      i++;
      t=A[i];
      A[i]=A[j];
      A[j]=t;
    }
  }
  t=A[i+1];
  A[i+1]=A[r];
  A[r]=t;
  return i+1;
}

 void quickSort(struct Card A[], int n, int p, int r){
  int q;
  if(p<r){
    q=partition(A,n,p,r);
    quickSort(A,n,p,q-1);
    quickSort(A,n,q+1,r);
  }
}


int main(){
  int n,i,v;
  struct Card A[MAX],B[MAX];
  char S[10];
  int stable=1;

  scanf("%d", &n);

  for(i=0;i<n;i++){
    scanf("%s %d", S, &v);
    B[i].suit=S[0];
    A[i].suit=B[i].suit;
    B[i].value=v;
    A[i].value=B[i].value;
  }
  
  mergeSort(A,n,0,n);
  quickSort(B,n,0,n-1);

  for(i=0;i<n;i++){
    if(A[i].suit!=B[i].suit)stable=0;
  }

  if(stable==1)printf("Stable\n");
  else if(stable==0)printf("Not stable\n");
  for(i=0;i<n;i++){
    printf("%c %d\n", B[i].suit, B[i].value);}

  return 0;
}




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

int main() {
  std::vector<int> v(3);
  rep(i,3) cin >> v.at(i);
  sort(v.begin(), v.end());
  cout << v.at(0) + v.at(1) << endl;
}


Measured memory_bytes: 3612
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <numeric>
#include <regex>

#define FOR(i, f, n) for(int (i) = (f); (i) < (n); (i)++)
#define RFOR(i, f, n) for(int (i) = (f); (i) >= (n); (i)--)
#define REP(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define RREP(i, n) for(int (i) = (n); (i) >= 0; (i)--)
#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define rrep(i, n) for(int (i) = (n); (i) >= 0; (i)--)
#define forin(i, a) for(auto i: (a))
#define p(...) printf(__VA_ARGS__); cout << endl;
#define in(...) __VA_ARGS__; input__(__VA_ARGS__);
#define input(...) in(__VA_ARGS__)
#define out(...) output__(__VA_ARGS__);
#define output(...) out(__VA_ARGS__)
#define list_input(x, n) x[(n)]; for(int (i) = 0; (i) < (n); (i)++) cin >> x[i];
#define lambda(a, b, c) [](auto const &a, auto const &b){ return c ;}
#define key(t, x, compare) [](const t &a, const t &b){ return a x compare b x ;}
#define unless(a) if(!(a))

using namespace std;

using pii = pair<int, int>;

template <class... T>
void input__(T &...a) {
  for(auto v: {&a...}) {
    cin >> *v;
  }
}

void output__(){
  cout << endl;
}

template <class Head, class... T>
void output__(Head const &v, T const &...a) {
  if(sizeof...(a) == 0) {
    cout << v;
  } else {
    cout << v << " ";
  }
  output__(a...);
}

int main(){
  int in(n);
  long long in(a);

  long long n1 = n + 1;
  for(long long i = 0; i < n1; i++) {
    long long ni = n1 - i;
    for(long long j = 0; j < ni; j++) {
      if(10000 * i + 5000 * j + 1000 * (n - i - j) == a) {
        out(i, j, n - i - j);
        exit(0);
      }
    }
  }
  out(-1, -1, -1);
}


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

typedef long long ll;
const int MAX = 210000;
const ll MOD = 1000000007;
int main(){
  int m,d;
  cin>>m>>d ;
  int ans=0;
  for(int i=1;i<=m;i++){
    for(int j=1;j<=d;j++){
      if(j/10>=2&&j%10>=2&&(j/10)*(j%10)==i)ans++;
    }
  }
  cout<< ans<<endl;
}


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

using namespace std;
void mysort(int arr[] , int n)
{
    for (int i = 0; i < n; ++i) {
        for (int j = i+1; j < n; ++j) {
            if(arr[i] > arr[j])
            {
                /// swap
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j]= temp;
            }
        }
    }
}

int main()
{
    int n, m  ;
    int a[1001] , b[1001] , pn[101] , sum = 0;
    cin >>n;
    for (int i = 0; i < n; ++i) {
        cin >>a[i];
        sum += a[i];
    }
    cin >> m;
    for (int i = 0; i < m; ++i) {
        cin >> pn[i];
        pn[i] --;
        cin >> b[i];
    }

    for (int i = 0; i < m; ++i) {

        cout << sum - a[pn[i]] + b[i] << endl;
    }

} 


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

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

// 自動でmodを取ってくれる整数型
// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;
// const int mod = 998244353;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

mint f(int n){ // 2のn乗
    if(n==0) return 1;
    mint x=f(n/2);
    x*=x;
    if(n%2==1) x*=2;
    return x;
}

// a^n mod を計算する
long long modpow(long long a, long long n) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

// indexは1から始まる！
// Binary Indexed Tree (Fenwick Tree)
// https://youtu.be/lyHk98daDJo?t=7960
template<typename T>
struct BIT {
  int n;
  vector<T> d;
  BIT(int n=0) {init(n);}
  void init(int nn) {n=nn;d.resize(nn+1);}
  void add(int i, T x=1) {
    for (i++; i <= n; i += i&-i) {
      d[i] += x;
    }
  }
  T sum(int i) { // [1,x]
    T x = 0;
    for (i++; i; i -= i&-i) {
      x += d[i];
    }
    return x;
  }
  T sum(int l, int r) { // [l,r)
    return sum(r-1) - sum(l-1);
  }
};
// BIT配列の宣言 N:配列数, n:各要素数+1;
// BIT<int> bit[N];
// rep(i,N) bit[i].init(n);

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


int main(){
    int n,k;
    cin>>n>>k;
    vector<int> a(n);
    rep(i,n) cin>>a[i];
    BIT<mint> dp[n+1];
    rep(i,n+1) dp[i].init(k+2);
    dp[0].add(k+1,1);
    rep(i,n){
        for(int j=1;j<=k+1;j++){
        dp[i+1].add(j,dp[i].sum(j,min(k+1,j+a[i])+1));
        }
    }
    cout<<dp[n].sum(1)<<endl;
}


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

int gcm(int a, int b){
    
    if(b > a){
        int tmp = a;
        a = b;
        b = tmp;
    }
    
    if(a % b == 0)return b;
    else return gcm(b, a % b);
}

int main(){
    int n,k;
    cin >> n >> k;
    vector<int> a(n);
    int maximam = 0;
    for(int i = 0; i < n; i++){
        cin >> a.at(i);
        if(a.at(i) > maximam)maximam = a.at(i);
    }
    
    string answer;
    
    
    if(n == 1){
        if(a.at(0) == k)answer = "POSSIBLE";
        else answer = "IMPOSSIBLE";
    }else{
        int g = gcm(a.at(0),a.at(1));
        for(int i = 2; i < n; i++){
            g = gcm(g,a.at(i));
        }
        
        if(k % g == 0 && maximam >= k)answer = "POSSIBLE";
        else answer = "IMPOSSIBLE";
        
    }
    
    cout << answer << endl;
    
}


Measured memory_bytes: 640
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <sstream>
#include <vector>
#include <map>
#include <set>
#include <complex>
#include <functional>
#include <utility>

#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i, m, n) for(int i = (m); i < (int)(n); ++i)
#define ALL(x) (x).begin(), (x).end()
#define INF 2000000000
//#define int long long int

#ifdef LOCAL
  #define eprintf(...) fprintf(stdout, __VA_ARGS__)
#else
  #define eprintf(...) 0
#endif

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned int uint;

int main() {
  map<char, char> opp;
  opp['U'] = 'D';
  opp['D'] = 'U';
  opp['L'] = 'R';
  opp['R'] = 'L';

  int sx, sy, tx, ty;
  cin >> sx >> sy >> tx >> ty;

  //UUR DDL LUUURRD RDDDLLU
  int dx = tx - sx;
  int dy = ty - sy;
  string ans;
  ans += string(dy, 'U') + string(dx, 'R');
  ans += string(dy, 'D') + string(dx, 'L');
  ans += "L" + string(dy+1, 'U') + string(dx+1, 'R') + "D"; 
  ans += "R" + string(dy+1, 'D') + string(dx+1, 'L') + "U"; 
  cout << ans << endl;

  return 0;
}


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

 int main() {
   string s, t;
   cin >> s >> t;
   vector<vector<int>> dp(3100, vector<int>(3100, 0));

   rep(i, 0, s.length()) {
     rep(j, 0, t.length()) {
       if (s.at(i) == t.at(j)) dp.at(i + 1).at(j + 1) = dp.at(i).at(j) + 1;
       else dp.at(i + 1).at(j + 1) = max(dp.at(i + 1).at(j), dp.at(i).at(j + 1));
     }
   }
   string ans = "";
   int S = s.length(), T = t.length();
   while(S > 0 && T > 0) {
     if (dp.at(S).at(T) == dp.at(S - 1).at(T)) S--;
     else if (dp.at(S).at(T) == dp.at(S).at(T - 1)) T--;
     else {
       ans = s.at(S - 1) + ans;
       S--;
       T--;
     }
   }
   cout << ans << endl;
 }


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

#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define spa << " " <<
#define lfs <<fixed<<setprecision(10)<<
#define test cout<<"test"<<endl;
#define fi first
#define se second
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define rep(i,n,m) for(ll i = n; i < (ll)(m); i++)
#define rrep(i,n,m) for(ll i = n - 1; i >= (ll)(m); i--)
typedef long long ll;
typedef long double ld;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const ll INF = 1e18;
using P = pair<ll, ll>;
template<typename T>
void chmin(T &a,T b){if(a>b)a=b;}
template<typename T>
void chmax(T &a,T b){if(a<b)a=b;}
void pmod(ll &a,ll b){a=(a+b)%MOD;}
void pmod(ll &a,ll b,ll c){a=(b+c)%MOD;}
void qmod(ll &a,ll b){a=(a*b)%MOD;}
void qmod(ll &a,ll b,ll c){a=(b*c)%MOD;}
ll median(ll a,ll b, ll c){return a+b+c-max({a,b,c})-min({a,b,c});}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
template<typename T1,typename T2>
void ans(bool x,T1 y,T2 z){if(x)cout<<y<<endl;else cout<<z<<endl;}  
template<typename T>
void debug(vector<vector<T>>v,ll h,ll w){for(ll i=0;i<h;i++)
{cout<<v[i][0];for(ll j=1;j<w;j++)cout spa v[i][j];cout<<endl;}};
void debug(vector<string>v,ll h,ll w){for(ll i=0;i<h;i++)
{for(ll j=0;j<w;j++)cout<<v[i][j];cout<<endl;}};
template<typename T>
void debug(vector<T>v,ll n){cout<<v[0];
for(ll i=1;i<n;i++)cout spa v[i];cout<<endl;};
template<typename T>
vector<vector<T>>vec(ll x, ll y, T w){
  vector<vector<T>>v(x,vector<T>(y,w));return v;}
ll gcd(ll x,ll y){ll r;while(y!=0&&(r=x%y)!=0){x=y;y=r;}return y==0?x:y;}
template<typename T>
void emp(map<T,ll>&m, T x){m.emplace(x,0).first->second++;}
vector<ll>dx={1,0,-1,0,1,1,-1,-1};
vector<ll>dy={0,1,0,-1,1,-1,1,-1};

int main(){
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);
  ll res=0,res1=INF,res2=-INF,buf=0;
  bool judge = true;
  ll n;cin>>n;
  vector<ll>a(n),b(n);
  rep(i,0,n)cin>>a[i];
  rep(i,0,n)cin>>b[i];
  ll k=0;
  rep(i,0,n)k+=b[i]-a[i];
  rep(i,0,n){
    if(a[i]<=b[i]){
      k-=(a[i]%2!=b[i]%2);
    }
    else{
      k-=a[i]-b[i];
    }
  }
  ans1(k>=0);
  return 0;
}

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

int main(){
    int n,k;
    cin >> n >> k;
    vector<ll> p(n);
    vector<ll> c(n);
    ll ans = -1e18;
    rep(i,n) cin >> p.at(i);
    rep(i,n) cin >> c.at(i);
    rep(i,n) p.at(i)--;

    rep(si,n){
        // find cycle
        int x = si;
        vector<int> cycle_score;
        ll tot = 0;
        while(true){
            x = p.at(x);
            cycle_score.push_back(c.at(x));
            tot += c.at(x);
            if(x == si) break;
        }
        int cycle_size = cycle_score.size();
        ll tmp = 0;
        rep(i,cycle_size){
            tmp += cycle_score.at(i);
            if(i + 1 > k) break;
            ll now = tmp;
            if(tot > 0){
                ll e = (k - (i+1)) / cycle_size;
                now += tot * e; 
            }
            ans = max(ans,now);
        }
    }
    cout << ans << endl;
}

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

using namespace std;

int main()
{
    int N, Y;
    cin >> N >> Y;

    for (int x = 0; x <= N; x++){
        for (int y = 0; y <= N - x; y++){
            int z = N - x - y;
            if (10000 * x + 5000 * y + 1000 * z == Y){
                cout << x << " " << y << " " << z << endl;
                return 0;
            }
        }
    }
    cout << "-1 -1 -1" << endl;
}



Measured memory_bytes: 256
R, G, B, N = map(int, input().split())
rmax = N // R
gmax = N // G
cnt = 0
for r in range(rmax + 1):
  for g in range(gmax + 1):
    rest = N - R * r - G * g
    if rest >= 0 and rest % B == 0:
      cnt += 1
print(cnt)


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

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

vector<int> s(100005) ;
vector<int> t(50005) ;

int binary_solve( int key, int n) {
  int left = 0 ;
  int right = n ;
  while ( left < right ) {
    int mid = ( left + right ) / 2 ;
    if ( s.at(mid) == key ) {
      return 1 ;
    }else if ( s.at(mid) < key ) {
      left = mid + 1 ;
    }else if ( key < s.at(mid) ) {
      right = mid ;
    }
  }
  return 0 ;
}

int main()
{
  int n ;
  cin >> n ;
  rep(i,n){
    cin >> s.at(i) ;
  }

  int q ;
  cin >> q ;
  rep(i,q) {
    cin >> t.at(i) ;
  }

  int cnt = 0 ;
  rep(i, q) {
    int key = t.at(i) ;
    if ( binary_solve( key, n ) ) {
      cnt++ ;
    }
  }
  cout << cnt << endl ;

  return 0 ;
}


Measured memory_bytes: 3360
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int get_max(int a, int b){
	if(a > b)
		return a;
	return b;
}
int main(){
	int a, b;
	while(~scanf("%d %d", &a, &b)){
		int c1 = a + b;
		int c2 = a - b;
		int c3 = a * b;
		int c4 = get_max(c1, c2);
		int c5 = get_max(c4, c3);
		printf("%d\n", c5);
	}
return 0;
}

Measured memory_bytes: 256