akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;

int main() {
	int n;
	scanf("%d", &n);
	ll a, b, c, d;
	scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
	for (int i=0 ; i<n ; i++) {
	//	cout <<"c, d, i, n = "<<c<<" "<<d<<" "<<i<<" "<<n<<endl;
		ll minn = c*i-d*(n-i-1);
		ll maxx = d*i-c*(n-i-1);
	//	cout <<"minn: "<<minn<<"   maxx: "<<maxx<<endl;
		if (a+minn <= b and a+maxx >= b) {
			printf("YES\n");
			return 0;
		}
	}
	printf("NO\n");
	return 0;
}

Measured memory_bytes: 256
def gcd(a, b):
    if a < b:
        a, b = b, a
    while a % b != 0:
        a, b = b, a % b
    return b


N, M = map(int, input().split())
S = input()
T = input()
x = gcd(N, M)
n = N // x
m = M // x

for i in range(x):
    if S[n*i] != T[m*i]:
        print(-1)
        exit()
print(N*M//x)


Measured memory_bytes: 9264
nn, kk = map(int, input().split())
r = nn - kk
b = kk
p = 10 ** 9 + 7

# for nCk calculation -----------------------

factorial = [0] * (nn + 1)
factorial[0] = 1
for i in range(nn):
    factorial[i + 1] = factorial[i] * (i + 1) % p
# 逆元


def cmb(n, k):
    # if (n == 1 or k == 1):
    if (n == 0 or k == 0):
        return 1
    if (n < 0 or k < 0):
        return 0

    return factorial[n] * pow(factorial[n - k], p - 2, p) * pow(factorial[k], p - 2, p) % p


# ---------------------------------------
for i in range(kk):
    #ans = comb(r + 1, i, exact=True) * comb(b - 1, i - 1, exact=True) % p
    if (r >= i):
        ans = (cmb(r + 1, i + 1) * cmb(b - 1, i)) % p
    else:
        ans = 0
    print(ans)


# https://img.atcoder.jp/abc132/editorial.pdf


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

int main(){
    char Tword[101],Hword[101];
    int num,Tscore=0,Hscore=0;
    int i;
    scanf("%d",&num);
    for(i=0;i<num;i++){
        scanf("%s %s",Tword,Hword);
        if(strcmp(Tword,Hword)==0){
            Tscore++;
            Hscore++;
        }else if(strcmp(Tword,Hword)>0){
            Tscore += 3;
        }else{
            Hscore += 3;
        }
        //printf("%d %d\n",Tscore,Hscore);
    }
    printf("%d %d\n",Tscore,Hscore);
    return 0;
}


Measured memory_bytes: 2024
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <valarray>
#include <vector>
using namespace std;

using ll = long long;
using ld = long double;
const int INF = 1e9;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;

int main()
{
  long long N;
  scanf("%lld", &N);
  vector<pair<ll, ll>> v(N);
  for (int i = 0; i < N; i++)
  {
    scanf("%lld", &v[i].first);
    scanf("%lld", &v[i].second);
  }
  sort(v.begin(), v.end());
  int a = -INF, b = INF, c = -INF, d = INF;
  for (int i = 0; i < N; ++i)
  {
    int t = v[i].first + v[i].second;
    if (a < t)
      a = t;
    if (b > t)
      b = t;
    t = v[i].first - v[i].second;
    if (c < t)
      c = t;
    if (d > t)
      d = t;
  }
  cout << max(a - b, c - d) << endl;

  return 0;
}


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

using namespace std;

int N, K, d, ma, a[100009];

int gcd (int a, int b)
{
    int r;
    while (b)
        r = a % b, a = b, b = r;
    return a;
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d %d", &N, &K), d = 0, ma = 0;
for (int i=1; i<=N; i++)
    scanf ("%d", &a[i]), d = gcd (d, a[i]), ma = max (ma, a[i]);
if (K <= ma && K % d == ma % d) printf ("POSSIBLE\n");
else printf ("IMPOSSIBLE\n");
return 0;
}


Measured memory_bytes: 768
#include <cstdio>
using namespace std;

int main()
{
	int x, y;
	scanf("%d %d", &x, &y);
	for (int i = 0; i <= x; ++i)
		if (2 * i + (x - i) * 4 == y)
			return printf("Yes"), 0;
	printf("No");

	return 0;
}


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

#define ull unsigned long long

#define min(a, b) ((a) > (b) ? (b) : (a))
#define max(a, b) ((a) > (b) ? (a) : (b))

bool isPalindrome(string s) {
    string t(s.rbegin(), s.rend());
    return s == t;
}

int main(void) {
    long K;
    long x;
    queue<long> q;
    cin >> K;
    for(long i = 1;i <= 9;i++) q.push(i);
    for(long i = 0;i < K;i++) {
        long mod, temp;
        x = q.front();
        mod = x % 10;
        temp = 10 * x + mod;
        q.pop();
        if(mod != 0) q.push(temp - 1);
        q.push(temp);
        if(mod != 9) q.push(temp + 1);
    }
    cout << x << endl;
    return 0;
}


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

int main () {
    int n; cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    set<int> x;
    rep(i, n) x.insert(a[i]);

    cout << x.size() << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<algorithm>
#include<utility>
#include<tuple>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<numeric>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define BIL ((ll)1e9)
#define MOD ((ll)1e9+7)
#define INF (1LL<<60)           //1LL<<63でオーバーフロー
#define inf (1<<29)             //1<<29でオーバーフロー

template<class T>
T GCD(T a, T b){
    if(a<b){
        T temp=a;
        a=b;
        b=temp;
    }
    T res=a%b;
    while(res!=0){
        a=b;
        b=res;
        res=a%b;
    }

    return b;
}

template<class T>
T LCM(T a, T b){
    T res=GCD(a,b);
    return a*b/res;
}

int main(int argc,char* argv[]){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);

    ll a,b,c,d;
    cin >> a >> b >> c >> d;

    ll cdlcm=LCM(c,d);

    ll csum=b/c-(a-1)/c;
    ll dsum=b/d-(a-1)/d;
    ll cdsum=b/cdlcm-(a-1)/cdlcm;

    cout << (b-a+1)-(csum+dsum-cdsum) << endl;

    return 0;
}


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

int main() {
    int N;
    std::cin >> N; 

    int T[N], sum = 0;
    for (int i = 0; i < N; ++i) {
        std::cin >> T[i];
        sum += T[i];
    }

    int M;
    std::cin >> M;

    int P, X;
    for (int i = 0; i < M; ++i) {
        std::cin >> P >> X;
        std::cout << sum - T[P-1] + X << std::endl;
    }

    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

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


Measured memory_bytes: 26248
/* おまじない　*/
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
typedef long long ll;
typedef long double ld;
using namespace std;
const ll MOD=pow(10,9)+7;
const ll INF=(1LL<<62);
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
const int ddx[8]={1,0,-1,-1,-1,0,1,1};
const int ddy[8]={1,1,1,0,-1,-1,-1,0};
void init(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
}
ll gcd(ll a,ll b){
    if(a<b)swap(a,b);
    if(a%b==0)return b;
    return gcd(a%b,b);
}
ll lcm(ll a,ll b){
    return a/gcd(a,b)*b;
}

class UnionFind{
public:
  vector< int > data;
 
  UnionFind(int sz) {
    data.assign(sz, -1);
  }
 
  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if(x == y) return (false);
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return (true);
  }

  bool isSame(int x,int y){
	  return find(x)==find(y);
  }
 
  int find(int k) {
    if(data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }
 
  int size(int k) {
    return (-data[find(k)]);
  }
};

int main(){
    init();
	
	ll D,G;cin>>D>>G;
	vector<ll>p(D);
	vector<ll>c(D);
	for(int i=0;i<D;i++){
		cin>>p[i]>>c[i];
	}

	ll ans=INF;

	for(int s=0;s<(1<<D);s++){
		ll nowG=0;
		ll nowans=0;
		priority_queue<ll>que;
		for(int i=0;i<D;i++){
			if((s>>i)&1){
				//全部買う
				nowG+=(100*(i+1)*p[i])+c[i];
				nowans+=p[i];
			}else{
				for(int j=0;j<p[i];j++)que.push(100*(i+1));
			}
			
		}
		while(nowG<G and que.size()!=0){
			nowG+=que.top();
			que.pop();
			nowans++;
		}
		if(nowG>=G)ans=min(ans,nowans);
	}
	cout<<ans<<endl;
}

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

using namespace std;
typedef long long int ll;
typedef pair<int, int> ii;
#define DEBUG freopen("in.txt", "r", stdin);

struct fastio {
    fastio() {
        ios::sync_with_stdio(false);
        cout << setprecision(10) << fixed;
        cin.tie(0);
    }
};

fastio _fast_io;

const int N = 105;
int n, ans;
int a[N];

int main() {
    ans = 1e9;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = -100; i <= 100; ++i) {
        int cost = 0;
        for (int j = 0; j < n; ++j) {
            cost += (i - a[j]) * (i - a[j]);
        }
        ans = min(ans, cost);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3652
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#define ll long long
using namespace std;
ll MAX=1e18;

int main(){
    int N;
    cin>>N;
    ll A[N],ans=1;
    for(int i=0;i<N;i++){
        cin>>A[i];
        if(A[i]==0){
            cout<<"0"<<endl;
            return 0;
        }
    }
    for(int i=0;i<N;i++){
        if(A[i]<=MAX/ans) ans*=A[i];
        else{
            cout<<"-1"<<endl;
            return 0;
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 4400
k,n = gets.chomp.split(" ").map(&:to_i);
a = gets.chomp.split(" ").map(&:to_i);

diff = k - (a.last)

if diff < a.first then
	diff = a.first
end

if diff < a.first + k - (a.last) then
	diff = a.first + k - (a.last)
end


for i in 1..(a.length-1) do
	if diff < a[i] - a[i-1] then
		diff = a[i] - a[i-1]
	end
end

puts k - diff

Measured memory_bytes: 28724
#include <algorithm>
#include <cctype>
#include <iostream>
#include <string>
#include <utility>
#include <vector>

using namespace std;

bool eq(const string &s, size_t pos, char c2) {
  return pos < s.length() and (s[pos] == c2 or s[pos] == '?');
}

bool is_greater(const string &s1, const string &s2) {
  if (s1 == "invalid") {
    return true;
  } else if (s2 == "invalid") {
    return false;
  }
  return s1.length() == s2.length()? s1 < s2: s1.length() < s2.length();
}

string compute(string s) {
  if ((isdigit(s[0]) and (s.length() == 1 or s[0] != '0')) or s[0] == '?') {
    for (size_t i = 0; i < s.length(); ++i) {
      if (not (isdigit(s[i]) or s[i] == '?')) {
        break;
      }
      if (i == s.length() - 1) {
        for (size_t j = 0; j < s.length(); ++j) {
          if (s[j] == '?') {
            s[j] = '9';
          }
        }
        return s;
      }
    }
  }
  if ((eq(s, 0, 'R') or eq(s, 0, 'L')) and eq(s, 1, '(') and eq(s, s.length() - 1, ')')) {
    vector<string> sv, cands;
    for (size_t i = 3; i < s.length() - 2; ++i) {
      if (eq(s, i, ',')) {
        string sl = compute(s.substr(2, i - 2));
        string sr = compute(s.substr(i + 1, s.length() - i - 2));
        if (sl != "invalid" and sr != "invalid") {
          if (eq(s, 0, 'L')) {
            cands.push_back(sl);
          }
          if (eq(s, 0, 'R')) {
          cands.push_back(sr);
          }
        }
      }
    }
    if (not cands.empty()) {
      return *max_element(cands.begin(), cands.end(), is_greater);
    }
  }
  return "invalid";
}

int main() {
  string s;
  cin >> s;
  cout << compute(s) << endl;
  return 0;
}

Measured memory_bytes: 3192
n, k = map(int, input().split())
c = {}
for i in range(n):
    a, b = map(int, input().split())
    if a in c.keys():
        c.update({a: c[a] + b})
    else:
        c[a] = b
# print(c)

cnt = 0
for i in sorted(list(c.keys())):
    cnt += c[i]
    if cnt >= k:
        print(i)
        exit()


Measured memory_bytes: 11104
#include<stdio.h>

#define MAX 100
#define INFTY (1<<21)
#define WHITE 0
#define GRAY 1
#define BLACK 2

int n,M[MAX][MAX];

int prim();
 
int main(){
  int i,j,e;
 
  scanf("%d",&n);
 
  for(i=0;i<n;i++){ 
    for(j=0;j<n;j++){
      scanf("%d",&e);
      M[i][j]=(e==-1)?INFTY:e;
    }
  }
  printf("%d\n",prim()); 

  return 0;
}
 
int prim(){
  int i,u,v,minv,sum=0;
  int d[MAX],p[MAX],color[MAX];
 
  for(i=0;i<n;i++){ 
    d[i]=INFTY;
    p[i]=-1;
    color[i]=WHITE;
  }
 
  d[0]=0;

  while(1){
    minv=INFTY;
    u=-1;
    for(i=0;i<n;i++){
      if(minv>d[i] && color[i]!=BLACK){
	u=i;
	minv=d[i];
      }
    }
    if(u==-1){
      break;
    }
    color[u]=BLACK;
    for(v=0;v<n;v++){ 
      if(M[u][v]!=INFTY && color[v]!=BLACK){
	if(d[v]>M[u][v]){
	  d[v]=M[u][v];
	  p[v]=u;
	  color[v]=GRAY;
	}
      }
    }
  }
  for(i=0;i<n;i++){ 
if(p[i]!=-1){
  sum+=M[i][p[i]];
      }
  }
  return sum;
}

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

int main(){
  int a, b, c, i, j, x, num;
  num = 0;
  cin>>a>>b>>c;
  for(i=a; i<=b; i++){
    for(j=1; i*j<c+1; j++){
      x = i * j;
      if (x == c){
        num += 1;
      }
    }
  }
  cout<<num<<endl;
  return 0;
}



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

#define ln                '\n'
#define all(dat)           dat.begin(), dat.end()
#define loop(i, to)        for (int i = 0; i < to; ++i)
#define cont(i, to)        for (int i = 1; i <= to; ++i)
#define circ(i, fm, to)    for (int i = fm; i <= to; ++i)
#define foreach(i, dat)    for (__typeof(dat.begin()) i = dat.begin(); i != dat.end(); ++i)

typedef long long          num;

using namespace std;

const int nsz = 2e5;
int n, a[nsz + 5];

int main() {
    ios::sync_with_stdio(0);
    cin >> n;
    cont (i, n) {
        cin >> a[i];
    }
    int cur = 0;
    cont (i, n) {
        if (a[i] == cur + 1) {
            ++cur;
        }
    }
    if (cur == 0) {
        cout << -1 << ln;
    } else {
        cout << n - cur << ln;
    }
}

Measured memory_bytes: 1024
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) {
    	FastScanner sc = new FastScanner(System.in);
    	int N = sc.nextInt();
    	int K = sc.nextInt();
    	int[] nums = new int[N];
    	for(int i = 0; i < N; ++i) {
    		nums[i] = sc.nextInt();
    	}
    	Arrays.sort(nums);
    	int left = 0, right = K - 1, min = Integer.MAX_VALUE;
    	while(right < N) {
    		min = Math.min(min, Math.abs(nums[right]) + nums[right] - nums[left]);
    		min = Math.min(min, Math.abs(nums[left]) + nums[right] - nums[left]);
    		left++;
    		right++;
    	}
    	System.out.println(min);
    }
}

class FastScanner {
    BufferedReader br;
    StringTokenizer st;
    boolean hasNext;

    public FastScanner(InputStream is) {
        br = new BufferedReader(new InputStreamReader(is));
        hasNext = true;
    }

    public String nextToken() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                hasNext = false;
                return "##";
            }
        }
        return st.nextToken();
    }

    String next = null;
    public boolean hasNext(){
        next = nextToken();
        return hasNext;
    }

    public int nextInt() {
        if (next == null){
            hasNext();
        }
        String more = next;
        next = null;
        return Integer.parseInt(more);
    }

    public long nextLong() {
        if (next == null){
            hasNext();
        }
        String more = next;
        next = null;
        return Long.parseLong(more);
    }

    public double nextDouble() {
        if (next == null){
            hasNext();
        }
        String more = next;
        next = null;
        return Double.parseDouble(more);
    }

    public String nextString(){
        if (next == null){
            hasNext();
        }
        String more = next;
        next = null;
        return more;
    }

    public char nextChar(){
        if (next == null){
            hasNext();
        }
        String more = next;
        next = null;
        return more.charAt(0);
    }
}

Measured memory_bytes: 36752
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		int d = sc.nextInt();

		boolean flg = true;

		if (Math.abs(a - b) > d)
			flg = false;

		if (Math.abs(b - c) > d)
			flg = false;

		if (Math.abs(a - c) <=d)
			flg = true;
		System.out.println(flg ? "Yes" : "No");
	}

}

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

int jump(int ind, vector<int> &stone, vector<int> &dp) {

	if (ind <= 0) {
		return 0;
	}

	if (dp[ind] != -1) {
		return dp[ind];
	}

	long low = abs(stone[ind] - stone[ind - 1]) + jump(ind - 1, stone, dp);
	long high = INT_MAX;

	if (ind - 2 >= 0) {
		high = abs(stone[ind] - stone[ind - 2]) + jump(ind - 2, stone, dp);
	}

	dp[ind] = min(low, high);

	return dp[ind];
}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

#ifndef ONLINE_JUDGE
	// for getting input from input.txt
	freopen("input1.txt", "r", stdin);
	// for writing output to output.txt
	freopen("output1.txt", "w", stdout);
#endif

	int n;
	cin >> n;

	vector<int>stone(n);
	vector<int>dp(n, -1);

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

	int answer = jump(n - 1, stone, dp);

	cout << answer << endl;

	return 0;
}

Measured memory_bytes: 10292
n = int(input())
ary = [list(map(int,input().split())) for i in range(n-1)]
time = 0
dp = [0]*n
for i in range(n-1):
    time = 0
    for j in range(i,n-1):
        if time <= ary[j][1]: time = ary[j][1]
        elif time > ary[j][1]:
            if time % ary[j][2] == 0:time += 0
            else:time += ary[j][2] - time % ary[j][2]
        time += ary[j][0]
    print(time)
print(0)

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

int main() {
  int a1,a2,a3;cin>>a1>>a2>>a3;
  cout << abs(a1-a2)+abs(a2-a3)+abs(a1-a3)-max(max(abs(a1-a2),abs(a1-a3)),abs(a2-a3)) << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <complex>
#include <algorithm>
#include <numeric>
#include <utility>
#include <tuple>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <random>
#include <iterator>

using namespace std;
using i64 = int64_t;
using i32 = int32_t;

i64 iabs(i64 x) {
    return x >= 0 ? x : -x;
}
int main() {
    int a, b, q;
    cin >> a >> b >> q;
    vector<i64> s(a + 2), t(b + 2);
    for (int i = 1; i <= a; ++i) cin >> s[i];
    for (int i = 1; i <= b; ++i) cin >> t[i];
    s[0] = t[0] = -1e11;
    s[a + 1] = t[b + 1] = 1e11;
    while (q--) {
        i64 x;
        cin >> x;
        auto sl = lower_bound(begin(s), end(s), x);
        auto sr = sl--;
        auto tl = lower_bound(begin(t), end(t), x);
        auto tr = tl--;
        i64 ss[] = {*sl, *sr};
        i64 ts[] = {*tl, *tr};
        i64 ans = 1e18;
        for (i64 s : ss) {
            for (i64 t: ts) {
                for (int i = 0; i < 2; ++i) {
                    ans = min(ans, iabs(x - s) + iabs(s - t));
                    swap(s, t);
                }
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

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

namespace AGC007B{
    public class Program{
        public static void Main(string[] args){
            var sr = new StreamReader();
            //---------------------------------
            var N = sr.Next<int>();
            var P = sr.Next<int>(N);

            var x = 1000000000;
            var a = 1;
            var b = 1000000000;

            var resA = new List<int>();
            var resB = new List<int>();
            for(var i = 1; i <= N; i++){
                var p = Array.IndexOf(P, i);
                if(a + b < x + p){
                    a += (x + p) - (a + b);
                }
                if(a + b > x + p){
                    b += (x + p) - (a + b);
                }
                resA.Add(a++);
                resB.Add(b--);
            }

            Console.WriteLine(string.Join(" ", resA));
            Console.WriteLine(string.Join(" ", resB));
            //---------------------------------
        }
    }

    public class StreamReader{
        private readonly char[] _c = {' '};
        private int _index = -1;
        private string[] _input = new string[0];
        private readonly System.IO.StreamReader _sr = new System.IO.StreamReader(Console.OpenStandardInput());

        public T Next<T>(){
            if(_index == _input.Length - 1){
                _index = -1;
                while(true){
                    string rl = _sr.ReadLine();
                    if(rl == null){
                        if(typeof(T).IsClass) return default(T);
                        return (T)typeof(T).GetField("MinValue").GetValue(null);
                    }
                    if(rl != ""){
                        _input = rl.Split(_c, StringSplitOptions.RemoveEmptyEntries);
                        break;
                    }
                }
            }
            return (T)Convert.ChangeType(_input[++_index], typeof(T), System.Globalization.CultureInfo.InvariantCulture);
        }

        public T[] Next<T>(int x){
            var ret = new T[x];
            for(var i = 0; i < x; ++i) ret[i] = Next<T>();
            return ret;
        }

        public T[][] Next<T>(int y, int x){
            var ret = new T[y][];
            for(var i = 0; i < y; ++i) ret[i] = Next<T>(x);
            return ret;
        }
    }
}

Measured memory_bytes: 9944
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define pll pair<ll,ll>
#define pint pll
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

const int MAX = 3010000;
const int MOD = 1e9+7;

long long fac[MAX], finv[MAX], inv[MAX];

void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll ans(ll r,ll c){
  ll ret=0;
  if(r==1){
    ret=c*(c+3);
    ret%=mod;
    ret*=inv[2];
    ret%=mod;
    return ret;
  }
  ret=COM(c+r+2,r+1);
  ll t=r+c+2;
  t%=mod;
  t*=-1;
  t+=mod;
  t%=mod;
  ret+=t;
  ret%=mod;
  return ret;
}

int main(){
  COMinit();
  ll r1,c1,r2,c2;
  cin >> r1 >> c1 >> r2 >> c2;
  ll x=ans(r2,c2),y=ans(r1-1,c1-1),z=mod-ans(r1-1,c2),w=mod-ans(r2,c1-1);
  z+=w;
  z%=mod;
  x+=z;
  x%=mod;
  x+=y;
  x%=mod;
  cout << x << endl;
return 0;}

Measured memory_bytes: 70784
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 long long N,M;
  cin >>N>>M;
  
  vector<vector<int>> data(N, vector<int>(2));
 
 
  for (int i = 0; i < N; i++) {
  cin >>data.at(i).at(0)>>data.at(i).at(1);   
  }
  
  sort(data.begin(),data.end());
   long long num=0;
     long long ans=0;
     int j=0;
  
  while(num!=M){
    long long Num=0;
   while(data.at(j).at(1)!=0){
     if(num==M){break;}
     data.at(j).at(1)--;
     num++;Num++;
   }
    
    ans+=data.at(j).at(0)*Num;
   
    j++;
  }
  cout <<ans<<endl;
}

Measured memory_bytes: 5888
#include <bits/stdc++.h>
using namespace std;
template <class T>
bool chmax(T& a, const T& b)
{
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T& a, const T& b)
{
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}

#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define all(x) (x).begin(), (x).end() //sortなどの引数を省略したい
#define F first
//#define S second

typedef long long ll;
const ll MOD = 1e9 + 7;
const int inf = 1000000;
const int minf = -1000000;
const ll lnf = 1e12;
const ll mlnf = -1e12;
const double e = 1e-10;

void debug_vector(vector<int>& v)
{
    int n = v.size();
    for (int i = 0; i < n; i++) {
        cout << v[i] << " ";
    }
    cout << endl;
}


//////////////////////
//// coding start ////
//////////////////////

// global variety

// function
void solve();

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    solve();
    return 0;
}

void solve(){
    int N; cin >> N;
    vector<long long> A(N);
    rep(i, N) cin >> A[i];

    int negative_cnt = 0;
    long long abs_smallest_num = lnf;
    long long ans = 0;
    rep(i, N){
        if (A[i] < 0){
            negative_cnt++;
        }
        ans += abs(A[i]);
        abs_smallest_num = min(abs_smallest_num, abs(A[i]));
    }
    if (negative_cnt % 2 != 0){
        ans -= abs_smallest_num * 2;
    }
    printf("%lld\n", ans);
        
}



Measured memory_bytes: 1024
import sys
input = sys.stdin.readline
mod=10**9+7
n,m=map(int,input().split())
x=list(map(int,input().split()))
y=list(map(int,input().split()))
xsum=0
for i in range(n):
    xsum+=x[-i-1]*(n-2*i-1)%mod
ysum=0
for i in range(m):
    ysum+=y[-i-1]*(m-2*i-1)%mod

print(xsum*ysum%mod)


Measured memory_bytes: 74468
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <bitset>
# include <complex>
# include <numeric>
#include <tuple>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
constexpr int INF = 2000000000;
constexpr int HINF = INF / 2;
constexpr double DINF = 100000000000000000.0;
constexpr long long LINF = 9223372036854775807;
constexpr long long HLINF = 4500000000000000000;
const double PI = acos(-1);
int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
#define ALL(x)   (x).begin(),(x).end()
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define mp       make_pair
#define eb       emplace_back
typedef pair<LL, LL> P;
typedef pair<P, P> PP;

long long gcd(long long a, long long b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}

long long lcm(long long a, long long b) {
	long long g = gcd(a, b);
	return a / g * b;
}

int main() {
	int n;
	cin >> n;
	LL ans = 1, a;
	for (int i = 0; i < n; i++) {
		cin >> a;
		ans = lcm(ans, a);
	}
	cout << ans << endl;
}

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

// M A F I A - M A F I A - M A F I A - M A F I A - M A F I A - M A F I A //

#define int                                       long long
#define lop(i,s,e)                                for(int i=s;i<(int)e;i++)
#define rlop(i,e,s)                               for(int i=e;i>=s;i--)
#define prvec(v)                                  lop(R15,0,v.size())cout << v[R15] <<" "; cout << endl;
#define prarr(arr,s1,e1)                          lop(R15,s1,e1)cout << arr[R15] << " "; cout << endl;

#define endl                                      '\n'
#define ff                                        first
#define ss                                        second
#define pii                                       pair<int,int>

#define pb                                        push_back
#define all(v)                                    v.begin(),v.end()

// M A F I A - M A F I A - M A F I A - M A F I A - M A F I A - M A F I A //

const int N = 3e6 + 7, M = 1000000007, inf = INT_MAX;
const long long INF = LLONG_MAX;

int n, Q;
int arr[N + 2];

#define db long double
void solve()
{
     db a, b;
     cin >> a >> b;
     db ans = a * b;
     // cout << fixed << setprecision(2) << ans << endl;
     cout << fixed << setprecision(0) << floor(ans) << endl;


}

int32_t main()
{
     ios_base::sync_with_stdio(0);   cin.tie(0);   cout.tie(0);

     int test = 1;
     // cin >> test;
     while (test--)solve();


}





Measured memory_bytes: 3788
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)
#define VL vector<ll>
#define VS vector<string>
#define VB vector<bool>
#define VP vector<pair<ll,ll>>
#define VVL vector<vector<ll>>
#define VVP vector<vector<pair<ll,ll>>>
#define PL pair<ll,ll>
#define ALL(v) (v).begin(), (v).end()

ll A,B,C;
int main(){
    cin>>A>>B>>C;
    ll tmp;
    //AtoB
    tmp=A;A=B;B=tmp;
    //AtoC
    tmp=A;A=C;C=tmp;
    cout<<A<<" ";
    cout<<B<<" ";
    cout<<C;

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
  int N, K;
  scanf("%d %d", &N, &K);

  double win = 0;
  double N1 = 1.0 / (double)N;
  for(int i = N; i >= 1; i--) {
    if(K <= i) {
      win += N1;
    } else {
      int div = 1;
      for(int j = i; j < K; j*=2) {
	div *= 2;
      }
      win += N1 * (1.0 / (double)div);
    }
    //printf("i=%d, win=%f\n", i, win);
  }

  printf("%.20lf\n", win);
  return 0;
}


Measured memory_bytes: 128
s = input()
acgt = ['A', 'C', 'G', 'T']
lenn = 0
maxlen = 0
for i in range(len(s)):
  if (s[i] in acgt):
    lenn += 1
  else:
    if (maxlen <= lenn):
      maxlen = lenn
    lenn = 0
if (maxlen <= lenn):
  maxlen = lenn
print(maxlen)

Measured memory_bytes: 3064
#include <stdio.h>

using namespace std;



int main(){
	
	int n;
	int A[100];
	int minj;
	int buf;
	int cnt = 0;

	scanf("%d", &n);
	for (int i = 0; i < n; i++)	scanf("%d", &A[i]);

	for (int i = 0; i < n; i++){
		minj = i;
		for (int j = i; j < n; j++){
			if (A[j] < A[minj]){
				minj = j;
			}
		}
		if (minj != i){
			buf = A[minj];
			A[minj] = A[i];
			A[i] = buf;
			cnt++;
		}
	}

	printf("%d", A[0]);
	for (int i = 1; i < n; i++) printf(" %d", A[i]);
	printf("\n%d\n", cnt);

	return 0;
}

Measured memory_bytes: 1028
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1LL << 50;
int main(void) {
int N, M;
cin >> N >> M;
const int NMAX = 1000;
 const int MMAX = 2000;
 int a[MMAX], b[MMAX];
 ll c[MMAX];

 for (int i = 0; i < M; ++i) {
 cin >> a[i] >> b[i] >> c[i];
 c[i] = -c[i];
 }

 ll dist[NMAX];

 for (int i = 0; i < N; ++i) {
 dist[i] = INF;
 }

 dist[0] = 0;


 for (int loop = 0; loop < N - 1; ++ loop) {
 for (int i = 0; i < M; ++i) {
    if (dist[a[i] - 1] == INF) continue;

 if (dist[b[i] - 1] > dist[a[i] - 1] + c[i]) {
 dist[b[i] - 1] = dist[a[i] - 1] + c[i];
 }
 }
 }

 ll ans = dist[N - 1];


 bool negative[NMAX];

 for (int i = 0; i < N; ++i) {
 negative[i] = false;
 }

 for (int loop = 0; loop < N ; ++ loop) {
 for (int i = 0; i < M; ++i) {
 if (dist[a[i] - 1] == INF) continue;

 if (dist[b[i] - 1] > dist[a[i] - 1] + c[i]) {
 dist[b[i] - 1] = dist[a[i] - 1] + c[i];
 negative[b[i] - 1] = true;
 }

 if (negative[a[i] - 1] == true) {
 negative[b[i] - 1] = true;
 }
 }
 }
 if (negative[N - 1])
 cout << "inf" << endl;
 else
 cout << -ans << endl;

 return 0;
 }

Measured memory_bytes: 256
// 2020-08-07 17:04:35
#include<bits/stdc++.h>
#ifdef LOCAL
#include "lib/debug.hpp"
#else
#define debug(...) 1
#endif
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define rep(i, n) REP(i, 0, (n))
#define repc(i, n) REPC(i, 0, (n))
#define REP(i, n, m) for (int i = (int)(n); i < (int)(m); i++)
#define REPC(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define REPCM(i, n, m) for (int i = (int)(n); i >= (int)(m); i--)
using namespace std;
using ll = long long;
using ld = long double;
using pr = pair<ll, ll>;
using vll = vector<ll>;
using vpr = vector<pr>;
using P = pair<int, int>;
template<class T> inline bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } else return false; }
template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }

bool ab[100000], ac[100000], bc[100000];
bool eq(char c1, char c2) {
  return (c1 == '?' || c2 == '?' || c1 == c2);
}
void answer() {
  string a, b, c;
  cin >> a >> b >> c;
  int az = a.size();
  int bz = b.size();
  int cz = c.size();
  rep(i, az) rep(j, bz) ab[i-j+50000] |= !eq(a[i], b[j]);
  rep(i, az) rep(j, cz) ac[i-j+50000] |= !eq(a[i], c[j]);
  rep(i, bz) rep(j, cz) bc[i-j+50000] |= !eq(b[i], c[j]);
  int ans = 6000;
  REPC(bi, -4000, 4000) REPC(ci, -4000, 4000) {
    if(ab[bi+50000]) continue;
    if(ac[ci+50000]) continue;
    if(bc[ci-bi+50000]) continue;
    int l = min({0, bi, ci});
    int r = max({az, bi + bz, ci + cz});
    chmin(ans, r - l);
  }
  cout << ans << '\n';
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  answer();
  return 0;
}

Measured memory_bytes: 3692
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define range(a) (a).begin(),(a).end()
#define print(A,x,n) rep(i,0,n){cout<<(i ? " ":"")<<A[i]x;}cout<<endl;
#define pprint(A,y,m,n) rep(j,0,m){print(A[j],y,n);}
const long mod=998244353;
const int siz=1e5;
const long inf=1e9;
int main(){
	int N; cin>>N;
	map<int,int> mp; int a;
	rep(i,0,N){ cin>>a; mp[a]++; }
	int cnt = 0;
	for(pair<int,int> p:mp){
		if(p.second % 2 == 1) cnt++;
	}cout<<cnt<<endl;
}

Measured memory_bytes: 4864
#include<iostream>
using namespace std;
int main(){
  int n;
  while(cin >>n){
    int solve = 0;
    for(int i=0; i<10; i++)
      for(int j=0; j<10; j++)
	for(int k=0; k<10; k++)
	  if(n-i-k-j>=0 && n-i-j-k<10) solve++;
    cout <<solve<<endl;
  }
  return 0;
}

Measured memory_bytes: 1164
class Stack():
    def __init__(self):
        self.el = []
        
    def add(self, el):
        self.el.append(el)
        
    def pop(self):
        return self.el.pop()

    def isEmpty(self):
        if len(self.el) == 0:
            return True
        else:
            return False

        
a = raw_input().split()
#print a
st = Stack()

for index in range(len(a)):
    #print a[index]
    if a[index] in ['+', '-', '*']:
        num1 = st.pop()
        num2 = st.pop()
        if a[index] == '+':
            st.add(int(num1) + int(num2))
        elif a[index] == '-':
            st.add(int(num2) - int(num1))
        else:
            st.add(int(num1) * int(num2))
    else:
        st.add(a[index])
    #print st.el

ans = st.pop()
print ans

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

int main(void){
    int K, S;
    cin >> K >> S;
    ll res = 0;
    REP(x,K+1){
        REP(y,K+1){
            int z = S - x - y;
            if(0<=z && z<=K){
                res++;
            }
        }
    }
    cout << res << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;

// #define int ll
#define REP(i,n) for (int i = 0; i < (n); ++i)
#define FORE(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define debug(x) cerr << #x << ": " << x << '\n'
#define hyphen() cerr << "--\n"

#define ALL(vec) (vec).begin(), (vec).end()
#define REVALL(vec) (vec).rbegin(), (vec).rend()

#define fst first
#define pb push_back

const int MOD = (int)1e9 + 7;
const int INF = numeric_limits<int>::max();

vector<P> next_points(P p) {
    vector<P> ans(4);

    ans.at(0) = make_pair(p.first, p.second+1);
    ans.at(1) = make_pair(p.first, p.second-1);
    ans.at(2) = make_pair(p.first-1, p.second);
    ans.at(3) = make_pair(p.first+1, p.second);

    return ans;
}

bool is_valid_point(int H, int W, vector<vector<bool>> passable, P p) {
    int y = p.first;
    int x = p.second;

    return 0 <= y && y < H && 0 <= x && x < W && passable.at(y).at(x);
}


signed main() {
    int H, W;

    cin >> H >> W;

    vector<vector<bool>> passable(H, vector<bool>(W, false));
    vector<vector<int>> distance(H, vector<int>(W, -1));
    distance.at(0).at(0) = 0;

    int ok_num = 0;
    REP(i, H) {
        string s;
        cin >> s;
        REP(k, W) {
            if (s.at(k) == '.') {
                passable.at(i).at(k) = true;
                ok_num += 1;
            }
        }
    }

    // (0, 0) から (H-1, W-1)までのキョリを求める
    // そのキョリ(path)以外のマスを塗る

    queue<P> q;
    q.push(make_pair(0, 0));

    while(!q.empty()) {
        P p = q.front();
        q.pop();

        int d = distance.at(p.first).at(p.second);

        for(auto next_p : next_points(p)) {
            int next_y = next_p.first;
            int next_x = next_p.second;

            if (!is_valid_point(H, W, passable, next_p)) {
                // debug(H);
                // debug(W);
                // int f = next_p.first;
                // int s = next_p.second;
                // debug(f);
                // debug(s);
                // cout << "aaaaaa" << endl;
                continue;
            }

            // 訪れたことあるマスならスキップ
            if (distance.at(next_y).at(next_x) != -1) {
                // debug(next_y);
                // debug(next_x);
                // cout << distance.at(next_y).at(next_x) << endl;
                // hyphen();

                continue;
            }

            // debug(next_y);
            // debug(next_x);
            // hyphen();

            distance.at(next_y).at(next_x) = d + 1;
            q.push(next_p);
        }
    }

    if (distance.at(H-1).at(W-1) == -1) {
            cout << "-1" << endl;
    } else {
        int ans = ok_num - (distance.at(H-1).at(W-1) + 1);
        cout << ans << endl;
    }
}


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

int main() {
  int n, j, k;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  // calc
  for (int i = 0; i < n - 1; i++) {
    cout << a[i] << " ";
  }
  cout << a[n - 1] << endl;
  
  for (int i = 1; i < n; i++) {
    j = i - 1;
    k = a[i];
    while (j >= 0 && a[j] > k) {
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = k;
    for (int l = 0; l < n - 1; l++) {
      cout << a[l] << " ";
    }
    cout << a[n - 1] << endl;
  }
  return 0;
}


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

int main() {
  int H, W;
  while (cin >> H >> W, H) {
    vector<vector<int>> a(H);
    for (int i = 0; i < H; ++i) {
      a[i].push_back(-1);
      string s; cin >> s;
      for (int j = 0; j < W; ++j) {
        if (s[j] == '*') a[i].push_back(j);
      }
      a[i].push_back(W);
    }
    int ans = 0;
    for (int h1 = 0; h1 < H; ++h1) {
      set<int> st;
      for (int h2 = h1; h2 < H; ++h2) {
        int l = h2 - h1 + 1;
        for (auto&& x : a[h2]) st.insert(x);
        int past = *st.begin();
        for (auto&& now : st) {
          ans = max(ans, l * (now - past - 1));
          past = now;
        }
      }
    }
    cout << ans << endl;
  }
  return 0;
}



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

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

struct UnionFind{
    vector<int> data;
    int __size;
    UnionFind(int sz) {
    data.assign(sz, -1);
    __size = sz;
  }
 
  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if(x == y) return (false);
    if(data[x] > data[y]) swap(x, y);//親は負でサイズを保存
    __size--;
    data[x] += data[y];
    data[y] = x;
    return (true);
  }
 
  int find(int k) {
    if(data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }

  bool same(int x, int y){
      return find(x) == find(y);
  }
 
  int size(int k) {
    return (-data[find(k)]);
  }

  int unum() {
    return (__size);
  }
};

int main(){ 
  int h, w;
  cin >> h >> w;
  vector<string> s(h);
  rep(i,h) cin >> s[i];
  map<int,ll> mp;
  UnionFind uf(h*w);
  vector<int> b; 
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      for (int k = 0; k < 2; k++) {
        int ny = i + dy[k], nx = j + dx[k];
        if (ny >= h || nx >= w) continue;
        if (uf.same(i*w+j,ny*w+nx)) continue;
        if (s[i][j] != s[ny][nx]) uf.unite(i*w+j, ny*w+nx); 
      }
    }
  }
  ll res = 0;
  rep(i,h) rep(j,w) if (s[i][j] == '#') mp[uf.find(i*w+j)]++;
  rep(i,h) rep(j,w) if (s[i][j] == '#') res += uf.size(i*w+j) - mp[uf.find(i*w+j)];
  cout << res << endl;
  return 0;
} 


Measured memory_bytes: 9728
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int k;
	cin>>k;
	string s;
	cin>>s;
	if(s.length()<=k)
	cout<<s;
	else
	{
		for(int i=0;i<k;i++)
		cout<<s[i];
		cout<<"...";
	}
}

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

#define fr(i,n) for(int i = 0; i<n; i++)
#define sz(v) (int)(v).size()
typedef long long ll;

const int N = 2e5+10;

struct Line{
	mutable ll m,k,p;
	bool operator<(const Line& o) const { return m<o.m;}
	bool operator<(ll x) const { return p<x;}
};

struct Cht : multiset<Line,less<>>{
	const ll inf = LLONG_MAX;
	ll div(ll a, ll b){
		return a/b - ( (a^b)<0 and a%b);
	}
	bool bad2(iterator x, iterator y){
		if(y==end()){
			x->p = inf;
			return 0;
		}
		if(x->m==y->m) x->p = (x->k>y->k)? inf : -inf;
		else x->p = div(x->k-y->k,y->m-x->m);
		return x->p>=y->p;
	}
	void add(ll m, ll k){
		auto z = insert({m,k,0}), y = z++, x = y;
		while(bad2(y,z)) z = erase(z);
		if(x!=begin() and bad2(--x,y)) bad2(x,erase(y));
		while((y=x)!=begin() and (--x)->p>=y->p) bad2(x,erase(y));
	}
	ll query(ll x){
		assert(!empty());
		auto l = *lower_bound(x);
		return l.m*x + l.k;
	}
};

ll h[N];

ll sq(ll x){
	return x*x;
}

int main(){
	ll n, c;
	cin >> n >> c;
	fr(i,n) scanf("%lld", h+i);
	
	Cht cht;
	cht.add(-h[0], -sq(h[0]));
	
	ll ans;
	for(int i = 1; i<n; i++){
		ll dp = c+sq(h[i]) - cht.query(-2*h[i]);
		ans = dp;
		cht.add(-h[i],-sq(h[i])-dp);
	}
	
	cout << ans << endl;
}




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

typedef long long ll;
typedef unsigned long long ull;
typedef string st;
typedef double db;
typedef vector<long long> vecll;
typedef vector<char> vechar;
typedef vector<string> vecst;

int main(){
    ll N, M;
    cin >> N >> M;
    vecll a(M), b(M);
    for(ll i = 0; i < M; i++) cin >> a.at(i) >> b.at(i);

    vecll ans(N);
    for(ll i = 0; i < M; i++){
        ans.at(a.at(i) - 1)++;
        ans.at(b.at(i) - 1)++;
    }
    for(ll i = 0; i < N; i++) cout << ans.at(i) << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int main(void)
{
	int l,x[11],i,a,n;
	char s[11];
	cin>>s;
	l=strlen(s);
	n=1000;
	for(i=0;i<l;i++) x[i]=s[i]-'0';
	for(i=0;i<l-2;i++){
		a=x[i]*100+x[i+1]*10+x[i+2];
		a=753-a;
		if(0>a) a=a*(-1);
		if(n>a) n=a;
	}
	cout<<n<<endl;
	return 0;
}

	

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int N;
    cin>>N;
    vector<string> vs(N,"");
    for(int i=0;i<N;i++){
        cin>>vs[i];
    }
    map<vector<int>,int> mp;
    for(int i=0;i<N;i++){
        vector<int> vt(26,0);
        for(int j=0;j<vs[i].length();j++){
            vt[vs[i][j]-'a']++;
        }
        if(mp.find(vt)==mp.end()){
            mp[vt]=1;
        }else{
            mp[vt]++;
        }
        vt.clear();
    }
    long long count=0;
    for(auto it=mp.begin();it!=mp.end();it++){
        long long num=it->second;
        if(num>1){
            count+=(num*(num-1)/2);
        }
    }
    cout<<count<<endl;
    return 0;
}

Measured memory_bytes: 25984
// Author: Sayantanu
#include <bits/stdc++.h>

using namespace std;

#define ll long long int
const int mod = 1e9 + 7;

int main() {
    //code
    ll n,w;
    cin>>n>>w;
    vector<ll> dp(w+1,0);
    ll weight,value;
    for(int i = 0 ; i < n; i++){
        cin>>weight>>value;
        for(int j = (w - weight) ; j>=0 ; j--){
            dp[j+weight] = max(dp[j+weight],dp[j]+value);
        }
    }
    cout<<dp[w]<<endl;
    return 0;
}

Measured memory_bytes: 3988
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
int main(int argc, char const *argv[]) {
    double t, x;
    cin >> t >> x;
    printf("%05f\n", t/x);
    return 0;
}

Measured memory_bytes: 256
n, a, b = gets.strip.split.map(&:to_i)

# 各桁の和を求める
def digit_sum(n)
    sum = 0
    while n > 0 do
        sum += n % 10
        n /= 10
    end
    sum
end

ans = (1..n)
        .map { |i| [i, digit_sum(i)] }
        .select { |d| a <= d[1] && d[1] <= b }
        .inject(0) { |sum, d| sum + d[0] }

puts ans

Measured memory_bytes: 14572
import java.util.Scanner;


public class Main {

	/**
	 * @param args
	 */
	static Scanner sc = new Scanner(System.in);
	static int n;
	static int []pm, pe, pj;
	public static void main(String[] args) {;
		// TODO 自動生成されたメソッド・スタブ
		while(read()) solve();
		
	}
	private static void solve() {
		// TODO 自動生成されたメソッド・スタブ
		for(int i=0; i<n; i++) {
			if(pm[i]==100 || pe[i]==100 || pj[i]==100) {
				System.out.println("A");
				continue;
			} else if(pm[i]+pe[i]>=180) {
				System.out.println("A");
				continue;
			} else if(pm[i]+pe[i]+pj[i]>=240) {
				System.out.println("A");
				continue;
			} else if(pm[i]+pe[i]+pj[i]>=210) {
				System.out.println("B");
				continue;
			} else if(pm[i]+pe[i]+pj[i]>=150 && (pm[i]>=80 || pe[i]>=80)) {
				System.out.println("B");
				continue;
			} else {
				System.out.println("C");
			}
		}
		
	}
	private static boolean read() {
		// TODO 自動生成されたメソッド・スタブ
		n = sc.nextInt();
		if(n==0) return false;
		pm = new int[n];
		pe = new int[n];
		pj = new int[n];
		for (int i = 0; i < n; i++) {
			pm[i] = sc.nextInt();
			pe[i] = sc.nextInt();
			pj[i] = sc.nextInt();
		}
	
		return true;
	}

	
}

Measured memory_bytes: 28264
#include<stdio.h>

int main(){
    int A,B,C;
    scanf("%d",&A);
    scanf("%d",&B);
    scanf("%d",&C);

    if(C<=A+B+1){
        printf("%d",B+C);
    }

    else{
        printf("%d",A+2*B+1);
    }
    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define sqr(x) ((x)*(x))
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define ld long double
#define vi vector<int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define debuge cerr<<"isok"<<endl
#define debug(x) cerr<<#x<<"="<<x<<endl
#define SS second
#define FF first
#define ls (k<<1)
#define rs (k<<1|1)
#define inf 0x3f3f3f3f
#define clr(a,x) memset(a,x,sizeof(a))
#define cpy(a,x) memcpy(a,x,sizeof(a))
#define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout);
using namespace std;

const int N=100005,M=100005,mod=1e9+7;
template<class T> inline void gmin(T &x,const T &y){if(x>y) x=y;}
template<class T> inline void gmax(T &x,const T &y){if(x<y) x=y;}
inline void ch(int &x,int y){x=(x+y)%mod;}
inline void read(int &x){
	x=0;char ch=getchar(),rev=0;
	while(ch>'9'||ch<'0') rev=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	x=rev?-x:x;
}
inline int exp(int x,int y){
	int ans=1;
	while(y){
		if(y&1) ans=(ll)ans*x%mod;
		x=(ll)x*x%mod;y>>=1;
	}return ans;
}

int n,a[N],mx,same=1;

int main(){
#ifdef rqgao2014
	freopen("input.txt","r",stdin);
#endif
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++){
		if(a[i]!=a[1]) same=0;
		gmax(mx,a[i]);
	}
	for(int i=1;i<=n;i++)
		if(mx-a[i]>1){puts("No");return 0;}
	if(same){
		if(a[1]==n-1||a[1]<=n/2) puts("Yes"); else puts("No");
		return 0;
	}
	int cnt=0;
	for(int i=1;i<=n;i++)
		if(a[i]!=mx) cnt++;
	if(cnt>=mx){puts("No");return 0;}
	if((mx-cnt)<=(n-cnt)/2)puts("Yes"); else puts("No");
	return 0;
}

Measured memory_bytes: 640