akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 1e5 + 5;
vector<int> adj[3 * MAXN];
int dis[3 * MAXN], n, m, S, T;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(n + v);
        adj[n + u].push_back(n + n + v);
        adj[n + n + u].push_back(v);
    }
    cin >> S >> T;
    memset(dis, -1, sizeof dis);
    queue<int> q({S});
    dis[S] = 0;
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(auto v : adj[u]) {
            if(dis[v] == -1) {
                dis[v] = dis[u] + 1;
                q.push(v);
            }
        }
    }
    if(dis[T] == -1)
        cout << "-1\n";
    else
        cout << dis[T]/3 << '\n';
}

Measured memory_bytes: 17792
import math
from functools import lru_cache

n=int(input())
@lru_cache()
def sosu(l):
  if l ==2:
    return 1
  elif l % 2==0 or l==1 or l==3/2 or l==0:
    return 0
  else:
    for d in range(3, math.floor(math.sqrt(l))+1,2):
      if l % d == 0:
        return 0
        break
    else:
      return 1

m=0
li=[]
for j in range(0,100001):
  m+=sosu(j)*sosu((j+1)/2)
  li.append(m)

for i in range(n):
  a,b=[int(i) for i in input().split()]
  print(li[b]-li[a-1])

Measured memory_bytes: 101080
#include <bits/stdc++.h>
using namespace std;
int main()
{
	string a,b;
	cin >> a >> b;
	int cont =0;
	for(int i =0; i < a.size(); ++i)
	{
		if(a[i] == b[i])
		{
			cont++;
		}
	}
	cout << cont;
	return 0;
}

Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let a: usize = read();
    let b: usize = read();
    let c: usize = read();
    let d: usize = read();
    let e: usize = read();
    let f: usize = read();

    let mut sf: Vec<bool> = vec![false; f + 1];
    let mut wf: Vec<bool> = vec![false; f + 1];

    for i in 0..f {
        if i % (a * 100) == 0 {
            wf[i] = true;
        }
    }
    for i in 0..f {
        if wf[i] && i + 100 * b < wf.len() {
            wf[i] = true;
        }
    }

    for i in 0..f + 1 {
        if i % c == 0 {
            sf[i] = true
        }
    }
    for i in 0..f + 1 {
        if sf[i] && i + d < sf.len() {
            sf[i + d] = true;
        }
    }

    let mut max_s = 0;
    let mut max_w = 100 * a;

    for i in 0..f + 1 {
        for j in 0..f + 1 {
            let si = sf[i];
            let wj = wf[j];
            if si && wj {
                if i + j <= f && j * e >= i * 100 {
                    if i * max_w > max_s * j {
                        max_s = i;
                        max_w = j;
                    }
                }
            }
        }
    }
    println!("{} {}", max_s + max_w, max_s);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using pll = pair<ll, ll>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(i) begin(i), end(i)

const int INF = 0x3fffffff;
const ll MINF = 0x7fffffffffff;
const ld DINF = numeric_limits<ld>::infinity();
const int MOD = 1000000007;
const int MODD = 998244353;
const ld EPS = 1e-9;
const ld PI = 3.1415926535897932;

template<class T> bool chmin(T &a, const T &b){ if(a > b){ a = b; return 1; } else return 0; }
template<class T> bool chmax(T &a, const T &b){ if(a < b){ a = b; return 1; } else return 0; }
template<class T> auto min(const T& a){ return *min_element(all(a)); }
template<class T> auto max(const T& a){ return *max_element(all(a)); }

ll gcd(ll a, ll b){ while(b){ ll c = b; b = a % b; a = c; } return a; }
ll lcm(ll a, ll b){ if(!a || !b) return 0; return a * b / gcd(a, b); }
ll pow_mod(ll n,ll k,ll m){ll r = 1;for(; k > 0;k >>= 1) {if (k & 1) r = (r * n) % m; n = (n * n) % m;}return r;}

//ここから。
int main(){
    ll N,M,K;
    cin >> N >> M >> K;
    vector<ll> A(N);
    vector<ll> B(M);
    ll ans = 0;
    vector<ll> sumA(N+1,0),sumB(M+1,0);
    rep(i,N) cin >> A[i];
    rep(i,M) cin >> B[i];
    rep(i,N) sumA[i+1] = sumA[i] + A[i];
    rep(i,M) sumB[i+1] = sumB[i] + B[i];

    ll j = M;
    rep(i,N+1){
        if( sumA[i] > K) break;
        while(sumB[j] + sumA[i] > K && j > 0) j--;
        ans = max(ans ,i+j);
    }
    cout << ans << endl;
}

Measured memory_bytes: 9580
import java.util.Scanner;

public class Main {
	final boolean DEBUG = false;
	class Node {
		int key;
		Node p, l, r;
		Node(int key) {
			this.key = key;
		}
		void insert(Node z) {
			Node y = null;
			Node x = this;
			while (x != null) {
				y = x;
				if (z.key < x.key) x = x.l;
				else			   x = x.r;
			}
			z.p = y;
			if (z.key < y.key) y.l = z;
			else			   y.r = z;
		}

		void delete(int key) {
			Node z = this;
			while (z != null) {
				if (key == z.key) break;
				if (key < z.key) z = z.l;
				else			 z = z.r;
			}
			if(DEBUG) {
				System.out.println("delete key: " + z.key);
			}
			Node y = z.p;
			if (z.l == null && z.r == null)
				if (y.l != null && y.l.key == z.key) y.l = null;
				else			 					 y.r = null;
			else if (z.l != null && z.r != null) {
				Node pre = this.getNextInNode(z.key);
				z.delete(pre.key);
				z.key = pre.key;
			} else {
				if (z.l != null) {
					if (y.l != null && y.l.key == z.key) y.l = z.l;
					else				                 y.r = z.l;
					z.l.p = y;
				} else {
					if (y.l != null && y.l.key == z.key) y.l = z.r;
					else			                     y.r = z.r;
					z.r.p = y;
				}
			}
		}

		boolean find(int key) {
			Node x = this;
			while (x != null) {
				if (key == x.key)
					return true;
				else if (key < x.key)
					x = x.l;
				else
					x = x.r;
			}
			return false;
		}
		void print() {
			this.inorder();
			System.out.println();
			this.preorder();
			System.out.println();
		}
		void preorder() {
			System.out.print(" " + this.key);
			if (this.l != null)
				this.l.preorder();
			if (this.r != null)
				this.r.preorder();
		}
		void inorder() {
			if (this.l != null)
				this.l.inorder();
			System.out.print(" " + this.key);
			if (this.r != null)
				this.r.inorder();
		}
		Node getNextInNode(int key) {
			Node n = null;
			if (this.l != null)
				n = this.l.getNextInNode(key);
			if (n != null)
				return n;
			if (this.key > key)
				return this;
			if (this.r != null)
				n = this.r.getNextInNode(key);
			if (n != null)
				return n;
			return n;
		}
	}
	void run() {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		Node t = null;
		for (int i = 0; i < n; i++) {
			String inst = scan.next();
			// set a root node
			if (i == 0) {
				int key = scan.nextInt();
				t = new Node(key);
				continue;
			}
			
			switch(inst) {
			case "insert":
				int key = scan.nextInt();
				if (DEBUG)
					System.out.println("insert: " + key);
				t.insert(new Node(key));
				break;
			case "find":
				int findKey = scan.nextInt();
				if (DEBUG)
					System.out.println("find: " + findKey);
				System.out.println(t.find(findKey) ? "yes" : "no");
				break;
			case "delete":
				int delKey = scan.nextInt();
				if (DEBUG)
					System.out.println("find: " + delKey);
				t.delete(delKey);
				break;
			case "print":
				if (DEBUG)
					System.out.println("print");
				t.print();
				break;
			}
		}
	}
	public static void main(String[] args) {
		new Main().run();
	}
}



Measured memory_bytes: 209900
#include<bits/stdc++.h>
using namespace std;
int ans,n,x[12];
void dfs(int d,long long sum){
    if(d==n){if(sum%2==0) ans++;return;}
    dfs(d+1,sum*(x[d+1]+1));
    dfs(d+1,sum*x[d+1]);
    dfs(d+1,sum*(x[d+1]-1));
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&x[i]);
    dfs(0,1);
    printf("%d\n",ans);
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>

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

int main() {
    char a;
    cin >> a;

    if (isupper(a)) {
        cout << "A" << endl;
    } else {
        cout << "a" << endl;
    }

    return 0;
}

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;
using namespace std;
const int MOD = 1000000007;
const int INF = 1010000000;
const double EPS = 1e-10;
const array<pair<int,int>,4> fd{make_pair(1,0),make_pair(-1,0),make_pair(0,1),make_pair(0,-1)}; 

int main(){
  string s;cin>>s;int n = s.length();
  bool ac = true;
  if(s[0] != 'A')ac = false;
  bool incC = false;
  repd(i,2,n-1){
    if(s[i] == 'C')incC = true;
  }
  if(!incC)ac = false;
  bool sudeC = false;
  repd(i,1,n){
    if(!sudeC && s[i] == 'C'){
      sudeC = true;
    }else if('a' > s[i] || s[i] > 'z'){
      ac = false;
    }
  }
  cout << (ac ? "AC" : "WA") << endl;
}


Measured memory_bytes: 256
#ifndef ___Class_Point
#define ___Class_Point

#include <cmath>

class Point
{
private:

	double x_;
	double y_;

public:

	Point() : x_(0), y_(0) { }

	explicit Point(double x, double y) : x_(x), y_(y) { }

	explicit Point(double x1, double y1, double x2, double y2) : x_(x2 - x1), y_(y2 - y1) { }

	double x() const { return x_; }
	double y() const { return y_; }

	void operator= (Point& p) { x_ = p.x_; y_ = p.y_; }
	
	Point operator+ (Point p) { return Point(x_ + p.x_, y_ + p.y_); }
	Point operator- (Point p) { return Point(x_ - p.x_, y_ + p.y_); }

	Point operator* (double s) { return Point(x_ * s, y_ * s); }
	Point operator/ (double s) { return Point(x_ / s, y_ / s); }
};

#endif

#ifndef ___Class_Vector
#define ___Class_Vector

typedef Point Vector;

double norm(Vector p1)
{
	return p1.x() * p1.x() + p1.y() * p1.y();
}

double abs(Vector p1)
{
	return sqrt(norm(p1));
}

double cross(Vector p1, Vector p2)
{
	return p1.x() * p2.y() - p1.y() * p2.x();
}

double dot(Vector p1, Vector p2)
{
	return p1.x() * p2.x() + p1.y() * p2.y();
}

#endif

#ifndef ___Computational_Geometry
#define ___Computational_Geometry

bool palarell(Vector p1, Vector p2)
{
	return cross(p1, p2) == 0;
}

bool palarell(Point p1_s, Point p1_e, Point p2_s, Point p2_e)
{
	return palarell(p1_e - p1_s, p2_e - p2_s);
}

bool orthogonal(Vector p1, Vector p2)
{
	return dot(p1, p2) == 0;
}

bool orthogonal(Point p1_s, Point p1_e, Point p2_s, Point p2_e)
{
	return orthogonal(p1_e - p1_s, p2_e - p2_s);
}

double dist_sqr(Point p1, Point p2)
{
	return pow(p2.x() - p1.x(), 2) + pow(p2.y() - p1.y(), 2);
}

double distance(Point p1, Point p2)
{
	return sqrt(dist_sqr(p1, p2));
}

Vector projection(Vector hypo, Vector base)
{
	return base * (dot(hypo, base) / norm(base));
}

Vector reflection(Vector hypo, Vector base)
{
	return base + (projection(hypo, base) - hypo) * 2.0;
}

#endif

#include <cstdio>

#pragma warning(disable: 4996)

int main()
{
	int x1, y1, x2, y2, x3, y3, q;

	scanf("%d", &x1);
	scanf("%d", &y1);
	scanf("%d", &x2);
	scanf("%d", &y2);

	Vector p(x1, y1, x2, y2);

	scanf("%d", &q);

	for (int i = 0; i < q; i++)
	{
		scanf("%d", &x3);
		scanf("%d", &y3);

		Vector a(x1, y1, x3, y3);

		Vector c = projection(a, p);

		printf("%.15f %.15f\n", x1 + c.x(), y1 + c.y());
	}

	return 0;
}

Measured memory_bytes: 2748
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string.h>
#include<iostream>
#define Max 2*100002
using namespace std;


vector<string>vec;

int main(){
	
	int n,i;
	string s;


	scanf("%d",&n);
	for(i=0;i<n;i++){
		cin >> s;
		sort(s.begin(),s.end());
		vec.push_back(s);
	}

	sort(vec.begin(),vec.end());

	long long int ans = 0,val=0;
	for(i=0;i<n-1;i++){
		if(vec[i] == vec[i+1])
			val++;
		else{
			ans += (val*(val+1))/2;
			val = 0;
		}
	}

	if(val > 0)
		ans += (val*(val+1))/2;

	printf("%lld\n",ans);

	return 0;
}

Measured memory_bytes: 5748
#include <bits/stdc++.h>
#include <string> 
using namespace std;
#define ll long long int
#define ld long double
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define mod 1000000007
#define mid 2019
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define fr(i,a,n) for(i=a;i<n;i++)
#define vll vector<ll>
#define pll pair<ll,ll>
#define vp vector<pll>
#define ub upper_bound
#define lb lower_bound
//#define map map<ll,ll>
#define mem(x,y) memset(x,y,sizeof(x))
#define all(v) v.begin(),v.end()
#define bs binary_search
#define qll queue<ll>
#define sll set<ll>
 
 
int main()
{
    fastio;
    ll n,i;
    cin>>n;
    ll a[n-1];
    for(i=0;i<n-1;i++)
    cin>>a[i];
    
    ll hash[n]={0};
    for(i=0;i<n-1;i++)
    {
        hash[a[i]]++;
    }
    for(i=0;i<n-1;i++)
    cout<<hash[i+1]<<endl;
    cout<<0<<endl;

}

Measured memory_bytes: 6752
#include <bits/stdc++.h>
using namespace std;
#define array_input int n;cin>>n;int a[n+1],i;for(i=1;i<=n;i++){cin>>a[i];}
#define array_output for(i=1;i<=n;i++){cout<<a[i]<<" ";}cout<<endl;
#define INF 2147483647
#define long_INF 18446744073709551615
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef long double ld;
const double pi=acos(-1);
const double eps=1e-6;

void read(int &x)
{
    x=0;
	char c=getchar();
    while(c<'0' || c>'9')c=getchar();
    while(c>='0' && c<='9')
	{
        x=x*10+c-'0';
        c=getchar();
    }
}

void write(int x)
{
    if(x==0)
	{
		putchar(48);
		return;
	}
    int len=0,dg[20];
    while(x>0)
	{
		dg[++len]=x%10;
		x/=10;
	}
    for(int i=len;i>=1;i--)
	{
		putchar(dg[i]+48);
	}
}

int main()
{
	int a,b,k;
	cin>>a>>b>>k;
	int i;
	for (i=a;i<=b;i++)
	{
		if (i-a<k || b-i<k)
		{
			cout<<i<<endl;
		}
	}
	return 0;
}

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

#define repi(i, a, b) for (int i = int(a); i < int(b); ++i)
#define rep(i, n) repi(i, 0, n)
#define all(x) (x).begin(), (x).end()

inline void Main() {
  int64_t n, q, tmp, b, c, s = 0;
  map<int64_t, int64_t> a;

  cin >> n;
  rep(i, n) {
    cin >> tmp;
    a[tmp] += 1;
    s += tmp;
  }
  cin >> q;

  rep(i, q) {
    cin >> b >> c;
    s += (c - b) * a[b];
    a[c] += a[b];
    a[b] = 0;
    cout << s << endl;
  }
}

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(20);
  Main();
  return 0;
}


Measured memory_bytes: 9456
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<math.h>
#include<string>
#include <iomanip>
#include<deque>

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;
const ll LINF = 1e18;
const int INF = 1e8;

using namespace std;


//マクロ定義
#define vvint(vec,n,m,l) vector<vector<int>> vec(n, vector<int>(m,l));	// lで初期化
#define vvll(vec,n,m,l) vector<vector<ll>> vec(n,vector<ll>(m,l));
#define vint vector<int>
#define pint pair<int,int>
#define rep(i,a) for(int i=0;i<(a);i++)
#define all(x) (x).begin(),(x).end()
#define debug system("pause")				//デバッグ用


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

	itn n, k;
	cin >> n >> k;

	if (n % k > 0)
	{
		cout << 1;
	}
	else
	{
		cout << 0;
	}
	cout << endl;

}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int A = scan.nextInt();
		int B = scan.nextInt();

		double eight = 0.08;
		double ten = 0.1;

		int start1 = (int)(A / eight);
		int start2 = (int)(B / ten);

		if (start1 == start2) {
			System.out.println(start1);
		}
		else {
			int start = Math.min(start1, start2);

			boolean exists = false;
			for (int i = 1; i < 11; i++) {
				int ans1 = (int)((start + i) * eight);
				int ans2 = (int)((start + i) * ten);
				if (ans1 == A && ans2 == B) {
					System.out.println(start + i);
					exists = true;
					break;
				}
			}
			if (!exists) {
				System.out.println(-1);
			}
		}
	}
}


Measured memory_bytes: 22996
def flg_fun(a):
    if a in [1,3,5,7,8,10,12]:
        b=1
    else:
        if a==2:
            b=2
        else:
            b=3
    return b


def assign_fun(x, y):
    if x==y:
        print("Yes")
    else:
        if flg_fun(x)==flg_fun(y):
            print("Yes")
        else:
            print("No")

a = input().split(" ")
assign_fun(int(a[0]), int(a[1]))

Measured memory_bytes: 3060
let n = Int(readLine()!)!

let a = readLine()!.split(separator: " ").map {
  Int($0)!
}

var array: [Int] = Array(repeating: 0, count: n)

for member in a {
  array[member-1] += 1
}

print(array.map { String($0) }.joined(separator: "\n"))


Measured memory_bytes: 18532
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

int main() {
    char c;
    cin >> c;
    char a;
    if (c == 'A') a = 'T';
    if (c == 'T') a = 'A';
    if (c == 'C') a = 'G';
    if (c == 'G') a = 'C';
    cout << a << endl;

    return 0;
}

Measured memory_bytes: 888
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair < ll, ll > PLL;
#define rep(i,n) for (int i = 0; i < (n); ++i)
int main() {
    ll n, h;
    cin >> n >> h;
    ll a = 0;
    vector<ll> b(n);
    rep(i, n) {
        ll tmp_a;
        cin >> tmp_a >> b[i];
        a = max(a, tmp_a);
    }
    sort(b.begin(), b.end());
    reverse(b.begin(), b.end());
    ll i = 0;
    ll ans = 0;
    ll resthp = h;
    while(1) {
        if ( resthp == 0 ) break;
        if ( b[i] < a ) {
            ans += ( resthp % a != 0 ) ? resthp / a + 1 : resthp / a;
            break;
        }
        resthp = max((ll)0, resthp - b[i]);
//        cout << b[i] << " " << resthp << endl;
        ++ans;
        ++i;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef long double ld;
typedef tree<ll,null_type,less<ll>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;

#define int ll
#define endl "\n"
#define all( x ) x.begin(), x.end()
#define rev_all( x ) x.rbegin(), x.rend()
#define fast ios::sync_with_stdio(0);cin.tie(0);

typedef unsigned long long ull;

const int mod = 1e9 + 7;
const int inf = 1e12 + 5;
const long double PI = 3.141592653589793;

void solve(){
  int x;
  cin >> x;
  cout << 10 - x / 200 << endl;
}
signed main(){
  fast;
  int t;
  t = 1;
  //cin >> t;
  while(t--){
    //cout << "Case #" << i << ":"<< endl;
    solve();
    //i++;
  }
}

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

#define f first
#define s second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ll long long
#define ull unsigned long long
#define db double
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pli pair<ll, int>
#define px pair<db, db>
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define input(a) for (auto& el : a) cin >> el;
#define output(a) cout << '!'; for (auto& el : a) cout << el << ' '; cout << '\n'; cout.flush();
#define sz(el) int(el.size())
#define sq(a) ((a) * (a))
#define xll bitset<128>
#define xmin(a,b) a = min(a, b)
#define xmax(a,b) a = max(a, b)
#define sun(a) sort(all(a)); a.resize(unique(all(a)) - a.begin());
/**/  /// extra
//#define forn(i,n) for (int i = 0; i < n; ++i)
//#define rforn(i,n) for (int i = n - 1; i >= 0; --i)
#define bn '\n'
#define vi vector<int>
#define vii vector<vi>
#define vl vector<ll>
#define vll vector<vl>
//#define G vector<vector<pii>>
#define GVE vector<vector<edge>>
#define usi unordered_set<int>
#define usp set<pii>
/**/

using namespace std;

const int INF = 1'000'000'017;
const ll LLINF = 1'000'000'000'000'000'017LL;
const ld inf = 1.0 / 0.0;
const ld eps = 1e-9;
const int MOD = 998244353;

//mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

//uniform_int_distribution<int> uid(l, r); [l, r]
//int x = uid(rng);

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

    ll n, a, b;
    cin >> n >> a >> b;
    if (a > b) {
        swap(a, b);
    }
    if ((b - a) % 2 == 0) {
        cout << (b - a) / 2;
    } else {
        cout << min(a + (b - a - 1) / 2, n - b + 1 + (n - (a + n - b + 1)) / 2);
    }
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())

const ll MAX = 510000;
const ll MOD = 1000000007;


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


int main(){
  ll N; cin>>N;
  vector<ll> a(N);
  rep(i,N) cin>>a[i];

  ll ans = 0;
  rep(i,N){
    while(a[i] % 2 == 0){
      ans++;
      a[i] /= 2;
    }
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <numeric>
#include <map>
using namespace std;

const double PI = acos(-1);

int main()
{
    int A, B, H, M;
    cin >> A >> B >> H >> M;

    double th = double(H * 60 + M) / 720 * 2 * PI;
    double tm = double(M) / 60 * 2 * PI;
    double xh = A * cos(th), yh = A * sin(th);
    double xm = B * cos(tm), ym = B * sin(tm);
    double dx = xh - xm, dy = yh - ym;
    double ans = sqrt(dx * dx + dy * dy);
    printf("%.10f\n", ans);


    return 0;
}

Measured memory_bytes: 4056
#include <bits/stdc++.h>
typedef long long i64;
using std::cout;
using std::endl;
using std::cin;

const int MOD = 1e9 + 7;
i64 mod_pow(i64 x, i64 n = MOD - 2) {
	i64 ret = 1;
	
	while(n) {
		if(n & 1) (ret *= x) %= MOD;
		(x *= x) %= MOD;
		n >>= 1;
	}
	
	return ret;
}

int main() {
	int n; cin >> n;
	std::string s; cin >> s;
	
	std::vector<std::vector<i64>> dp(n + 1, std::vector<i64>(n + 1, 0)); dp[0][0] = 1;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			dp[i + 1][std::max(0, j - 1)] += dp[i][j];
			dp[i + 1][j + 1] += dp[i][j] * 2;
			
			dp[i + 1][std::max(0, j - 1)] %= MOD;
			dp[i + 1][j + 1] %= MOD;
		}
	}
	
	cout << dp[n][s.size()] * mod_pow(mod_pow(2, s.size())) % MOD << endl;
	return 0;
}


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

#include <atcoder/all>
#define For(i, a, b) for (int(i) = (int)(a); (i) < (int)(b); ++(i))
#define rFor(i, a, b) for (int(i) = (int)(a)-1; (i) >= (int)(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
using namespace atcoder;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pll;
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
T div_floor(T a, T b) {
    if (b < 0) a *= -1, b *= -1;
    return a >= 0 ? a / b : (a + 1) / b - 1;
}
template <class T>
T div_ceil(T a, T b) {
    if (b < 0) a *= -1, b *= -1;
    return a > 0 ? (a - 1) / b + 1 : a / b;
}

constexpr lint mod = 1000000007;
constexpr lint INF = mod * mod;
constexpr int MAX = 200010;

int main() {
    int n, q;
    scanf("%d%d", &n, &q);
    dsu uf(n);
    rep(_, q) {
        int t, u, v;
        scanf("%d%d%d", &t, &u, &v);
        if (t == 0)
            uf.merge(u, v);
        else
            printf("%d\n", uf.same(u, v));
    }
}

Measured memory_bytes: 4096
#include<cstdio>
#include<queue>
using namespace std;
inline int read()
{
	int x;char c;
	while((c=getchar())<'0'||c>'9');
	for(x=c-'0';(c=getchar())>='0'&&c<='9';)x=x*10+c-'0';
	return x;
}
#define N 262144
#define INF 0x3FFFFFFF
#define mp make_pair
#define tp pq.top()
#define F first
#define S second
int t[N*2+5],t1[N*2+5],t2[N*2+5],p[N];
priority_queue<pair<pair<int,int>,pair<int,int> > > pq;
void build(int*t){for(int i=N;--i;)t[i]=min(t[i<<1],t[i<<1|1]);}
int query(int*t,int l,int r)
{
	int res=INF;
	for(l+=N-1,r+=N+1;l^r^1;l>>=1,r>>=1)
	{
		if(~l&1)res=min(res,t[l+1]);
		if( r&1)res=min(res,t[r-1]);
	}
	return res;
}
void push(int l,int r)
{
	if(l>r)return;
	int x=query(l&1?t1:t2,l,r);
	pq.push(mp(mp(-x,-query(l&1?t2:t1,p[x]+1,r)),mp(l,r)));
}
int main()
{
	int n=read(),i,x,y,l,r;
	for(i=1;i<=n;++i)p[x=read()]=i,t[i+N]=x,t1[i+N]=i&1?x:INF,t2[i+N]=i&1?INF:x;
	build(t);build(t1);build(t2);
	for(push(1,n);!pq.empty();)
	{
		x=-tp.F.F;y=-tp.F.S;l=tp.S.F;r=tp.S.S;
		printf("%d %d ",x,y);pq.pop();
		push(l,p[x]-1);push(p[x]+1,p[y]-1);push(p[y]+1,r);
	}
}

Measured memory_bytes: 8948
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin>>n;
    vector<vector<int> >g;
    g.resize(n);
    int m;
    cin>>m;
    while(m--){
        int x,y;
        cin>>x>>y;
        g[--x].push_back(--y);
        g[y].push_back(x);
    }
    set<int>have;
    int ans=0;
    for(int i=0;i<n;i++){
        
        for(int j=0;j<g[i].size();j++){
            int v=g[i][j];
            if(have.find(v)!=have.end()){
                have.clear();ans++;
            }
        }
        have.insert(i);
    }
    cout<<ans;
}


Measured memory_bytes: 7548
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

int a,b;
char map[10][10];
int book[10][10];
int h[10],l[10];
int xy[20],xz[20];

void print()
{
    for(int i=0; i<=7; i++)
    {
        for(int j=0; j<=7; j++)
        {
            if(book[i][j]==1)
            {
                if(h[i]!=j)
                    return ;
            }
        }
    }

    for(int i=0; i<=7; i++)
    {
        for(int j=0; j<=7; j++)
        {
            if(h[i]==j)
                printf("Q");
            else
                printf(".");
        }
        printf("\n");
    }

    return ;
}

void dfs(int n)
{
    if(n==8)
    {
        print();
        return ;
    }

    for(int i=0; i<=7; i++)
    {
        if(l[i]==0&&xy[n+i]==0&&xz[7+n-i]==0)
        {
            h[n]=i;
            l[i]=xy[n+i]=xz[7+n-i]=1;
            dfs(n+1);
            l[i]=xy[n+i]=xz[7+n-i]=0;
        }
    }
}

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        memset(book,0,sizeof book);
        memset(map,'.',sizeof map);
        memset(h,0,sizeof h);
        memset(l,0,sizeof l);
        memset(xy,0,sizeof xy);
        memset(xz,0,sizeof xz);
        for(int i=0; i<n; i++)
        {
            scanf("%d%d",&a,&b);
            book[a][b]=1;
        }
        dfs(0);
        h[0]=1;
    }
    return 0;
}



Measured memory_bytes: 2684
def main():
	n,k,a = map(int,input().split())
	
	t = True
	i = 0
	done = 0
	time = 0
	while t:
		if n > done:
			i += 1
			done += k
			time += a
		else:
			break
	print(time)

if __name__ == '__main__':
	main()

Measured memory_bytes: 61760
import copy
import heapq

tmp = list(map(int, input().split()))
n = tmp[0]
k = tmp[1]
v = list(map(int, input().split()))

a = [[0] * (k+1) for i in range(n+1)]
b = [[0] * (k+1) for i in range(n+1)]
ha = []
hb = []
for i in range(1, n+1):
  a[i][0] = a[i-1][0] + v[i-1]
  b[i][0] = b[i-1][0] + v[n-i]
  if v[i-1] < 0:
    heapq.heappush(ha, v[i-1])
  if v[n-i] < 0:
    heapq.heappush(hb, v[n-i])
  cha = copy.deepcopy(ha)
  chb = copy.deepcopy(hb)
  for j in range(1, k+1):
    if len(cha) != 0:
      a[i][j] = a[i][j-1] - heapq.heappop(cha)
    else:
      a[i][j] = a[i][j-1]
  for j in range(1, k+1):
    if len(chb) != 0:
      b[i][j] = b[i][j-1] - heapq.heappop(chb)
    else:
      b[i][j] = b[i][j-1]

maxv = 0
for i in range(0, k+1):
  for j in range(0,min(n+1, i+1)):
    for l in range(0,min(n+1, k-i+1)):
      tmp = a[j][i-j] + b[l][k-i-l]
      if (j+l) <= n and tmp > maxv:
        maxv = tmp
print (maxv)

Measured memory_bytes: 45148
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#include <assert.h>
typedef int64_t ll;
typedef uint64_t ull;
int acs(const void *a, const void *b){return *(int*)a - *(int*)b;} /* 1,2,3,4.. */
int des(const void *a, const void *b){return *(int*)b - *(int*)a;} /* 8,7,6,5.. */
#define min(a,b) (a < b ? a: b)
#define max(a,b) (a > b ? a: b)

#define MAXN (100000)
#define MOD (1000000007)

// べき乗余
int64_t modpow(int64_t b, int64_t e)
{
    int64_t result = 1;
    while(e>0)
    {
        if(e&1) result = (result * b) % MOD;
        e >>= 1;
        b = (b * b) % MOD;
    }
    return result;
}

// 組み合わせ数
// nCk % MOD
ll cf[MAXN+1]; // 1*2*3*...*i
ll ci[MAXN+1]; // 1/ 1*2*3*...*i
void CombInit(ll n)
{
    cf[0] = 1;
    for(int i=1;i<=n;i++) cf[i] = cf[i-1] * i %MOD;
    ci[n] = modpow(cf[n],MOD-2);
    for(int i=n-1;i>=0;i--) ci[i] = ci[i+1] * (i+1) %MOD;
}
ll Comb(ll a,ll b)
{
    return cf[a]*ci[b]%MOD*ci[a-b]%MOD;
}


int d[MAXN];
int main(void)
{
    int n,k;
    scanf("%d %d",&n,&k);
    int r = n-k;
    CombInit(n);
    for(int i=1;i<=k;i++)
    {
        ll ans = Comb(r+1,i) * Comb(k-1,i-1) % MOD;
        printf("%ld\n",ans);
    }
    return 0;
}


Measured memory_bytes: 256
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
//#pragma GCC optimize(2)
//#include <immintrin.h>
#include<bits/stdc++.h>
using namespace std;
int main()
{
   	deque<int> a;
   	int n,o;
   	cin >> n;
   	for(int i = 1;i <= n;i ++)
   	{
   		cin >> o;
   		if(i & 1)
   			a.push_back(o);
   		else
   			a.push_front(o);
	}
	if(n & 1)
		reverse(a.begin(), a.end());	
	for(int i = 0;i < n;i ++)
	{
		cout << a[i] << " ";
	}
	puts("");
    return 0;
}

Measured memory_bytes: 2944
N = int(input())
n = [input().split() for _ in range(N)]

all_info = [[[0 for _ in range(10)] for _ in range(3)] for _ in range(4)]

def change_room(info):
    info = [int(i) for i in info]
    info_dic = {"all_info": all_info,
                "buil": info[0]-1,
                "loc" : info[1]-1,
                "room": info[2]-1,
                "num" : info[3]}

    exec("all_info[buil][loc][room] += num", info_dic)

for i in n:
    change_room(i)

for num, i in enumerate(all_info):
    for j in i:
        j = [str(i) for i in j]
        print(" " + (" ".join(j)))
    if num < 3: 
        print("#"*20)


Measured memory_bytes: 5612
in1 = int(input())
in2 = [input().strip().rsplit(" ") for i in range(in1)]
in3 = input()
time = 0 

in2a = list(zip(*in2))

inde = in2a[0].index(in3)

for times in range(inde+1, in1):
    time += int(in2[times][1])
print(time)

Measured memory_bytes: 3060
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
#include <string.h>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <tuple>
#include <stdlib.h>
using namespace std;
#define PI 3.14159265358979
typedef long long int ll;

int main()
{
	int ans=0;
    string S;
    cin>>S;
    for(int i=0;i<S.length()/2;i++)
    {
    	if(S[i]!=S[S.length()-i-1])ans++;
    }
    cout<<ans;
}


Measured memory_bytes: 256
using System;
using System.Linq;

public class Program {
    public static void Main() {
        var n = int.Parse(Console.ReadLine());
        var slimes = Console
            .ReadLine()
            .Split(' ')
            .Select(s => long.Parse(s))
            .OrderBy(l => l)
            .ToArray();

        var sums = new long[n];
        sums[0] = slimes[0];

        for (int i = 1; i < n; i++) {
            sums[i] = sums[i - 1] + slimes[i];
        }

        var t = CalculateT(n, sums, slimes);

        Console.WriteLine(n - t);
    }

    private static int CalculateT(int n, long[] sums, long[] slimes) {
        for (int k = n - 2; k >= 0; k--) {
            if (sums[k] * 2 < slimes[k + 1]) {
                return k + 1;
            }
        }
        return 0;
    }
}


Measured memory_bytes: 30172
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC omodtimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
using namespace __gnu_pbds;
using namespace std;
 
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<long long ,long long> ii; 	
typedef complex<long double> com;
 
const ll mod = 1e9+7;


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll a,b;
	cin >> a >> b;
	for (ld z=1;z<=(1e6);z++){
		if (floor(z*ld(0.08)) == a && floor(z*ld(0.1))== b){
			cout << z << endl;
			return 0;
		}
	}
	cout << -1 << endl;
}


Measured memory_bytes: 512
#include <cmath>
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
int main() {
	int N;
	cin >> N;
	vector<string> S(N);
	for (int i = 0; i < N; ++i) {
		cin >> S[i];
	}
	sort(S.begin(), S.end());
	S.erase(unique(S.begin(), S.end()), S.end());
	cout << S.size() << endl;
	return 0;
}

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

using namespace std;
typedef long long ll;

#define INF (long long)(1e9+7)
#define REP(i,n) for(ll i = 0; i < n; i++)
#define REP1(i,n) for(ll i = 1; i <= n; i++)

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



int main(void)
{
  ll n;
  cin >> n;
  ll p = n * 100 / 108;
  for(ll i = p - 5; i < p + 5; i ++) {
    ll p2 = i * 108 / 100;
    if(n == p2) {
      cout << i << endl;
      return 0;
    }
  }
  cout << ":(" << endl;
}


Measured memory_bytes: 256
#pragma once
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <deque>
typedef long long ll;
using namespace std;

int r, g, b;
const int INF = 10e8;

struct root {
	int cost;
	vector<int> ft;
};
root d[101][101];
int origin[101][101];
int res = 0;
bool check[101][101];
void recur(int i, int j) {

	if (check[i][j]) return;
	if (d[i][j].ft.size() == 2) {
		res++;
	}
	else if(d[i][j].ft.size() == 3){
		recur(d[i][j].ft[0], d[i][j].ft[1]);
		recur(d[i][j].ft[1], d[i][j].ft[2]);
	}
	check[i][j] = true;
}
void CandidatesofNoShortestPaths() {

	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		for (size_t j = 1; j <= n; j++)
		{
			d[i][j].cost = INF;
			origin[i][j] = 0;
		}
	}
	
	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		d[a][b].cost = c;
		d[a][b].ft = { a,b };
		d[b][a].cost = c;
		d[b][a].ft = { b,a };
		origin[a][b] = 1;
		origin[b][a] = 1;
	}

	for (int v = 1; v <= n; v++)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				if (d[i][j].cost > d[i][v].cost + d[v][j].cost) {
					d[i][j].cost = d[i][v].cost + d[v][j].cost;
					d[i][j].ft = { i,v,j };
				}
			}
		}
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			recur(i, j);
		}
	}

	cout << (m  - res / 2) << endl;
}

int main() {
	CandidatesofNoShortestPaths();
	return 0;
}



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

int f(ll x, ll a, ll b){
    return (a*x)/b - a*(x/b);
}

void solve(){
    ll a, b, n;
    cin >> a >> b >> n;
    cout << f(min(b-1, n), a, b) << '\n';
}

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


Measured memory_bytes: 3600
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		String N=sc.nextLine();
		char t[]=N.toCharArray();
		int n=Integer.parseInt(N);
		int comp=0;
		int ans=0;
		int T[]=new int[t.length];
		for(int i=0;i<t.length;i++){
			T[i]=Character.getNumericValue(t[i]);
		}
		comp=T[0]*111;
		if(n<=comp){
			ans=comp;
		}else if(n>comp){
			ans=comp+111;
		}
		System.out.print(ans);
	}

}

Measured memory_bytes: 23764
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mian main
using namespace std;
int a,t,Max = -1;
char c[110];
int mian() {
	scanf("%d%s",&a,c);
	for(int i = 0 ; i < a ; ++ i){
		if(c[i] == 'I') {
			t ++;
		}
		else t --;
		Max = max(Max,t);
	}
	if(Max == -1) Max = 0;
	printf("%d",Max);
	return 0;
}

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

int main() {

    int x, y;
    cin >> x >> y;
    int c = x * 2;
    for (int i = 0; i <= x; ++i) {
        if (c == y) {
            cout << "Yes" << endl;
            return 0;
        }
        c += 2;
    }
    cout << "No" << endl;
    return 0;
}

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

int main(){
     int a,b;
     cin >> a>>b;
     if(a+b>=24) cout << a+b-24 <<endl;
     else cout << a+b <<endl;        
 }

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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N;
  cin >> N;
  int k = -1;
  for (int i = 1; i < N + 1; i++) {
    if (i * (i + 1) / 2 == N) {
      k = i + 1;
      break;
    }
  }
  if (k == -1) {
    cout << "No" << '\n';
    return 0;
  }
  cout << "Yes" << '\n';
  cout << k << '\n';
  vector<vector<int>> S(k);
  int x = 1;
  for (int i = 0; i < k; i++) {
    for (int j = i + 1; j < k; j++) {
      S[i].emplace_back(x);
      S[j].emplace_back(x);
      x++;
    }
  }
  for (int i = 0; i < k; i++) {
    cout << S[i].size() << ' ';
    for (const auto &v : S[i]) {
      cout << v << (&v == &S[i].back() ? '\n' : ' ');
    }
  }
  return 0;
}


Measured memory_bytes: 4252
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define ll long long

ll dp[105][100100];
int ar[105];

inline ll add(ll a, ll b)
{
	a = ((a % MOD) + MOD) % MOD;
	b = ((b % MOD) + MOD) % MOD;
	return (a + b) % MOD;
}

inline ll sub(ll a, ll b)
{
	a = ((a % MOD) + MOD) % MOD;
	b = ((b % MOD) + MOD) % MOD;
	return ((a - b) % MOD + MOD) % MOD;
}

int main()
{

	int n, k;
	scanf("%d", &n); scanf("%d", &k);

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

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

	for (int i = 1; i < n; ++i)
	{
		dp[i][0] = 1;
		for (int j = 1; j <= k; ++j)
		{
			dp[i][j] = add(dp[i][j - 1] , dp[i - 1][j]);
			if (j > ar[i])
				dp[i][j] = sub(dp[i][j], dp[i - 1][j - 1 - ar[i]]);
		}
	}

	cout << dp[n - 1][k];




	return 0;
}

Measured memory_bytes: 80128
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <stack>
#include <numeric>
#include <algorithm>
#include <tuple>
#include <stdio.h>
#include <bitset>
#include <limits.h>
#include <complex>
#include <deque>
#include <iomanip>
#include <list>
using namespace std;
#define pi pair<int32,int32>
#define pl pair<int64,int64>
#define chmax(a,b) (a<b ? a=b:0)
#define chmin(a,b) (a>b ? a=b:0)
#define en cout << endl //セミコロンつけろ
//#define MM 1000000000
//#define MOD MM+7
const int MM = 1e9;
const int MOD = MM+7;
const long double PI = acos(-1);
const long long INF = 1e15;
int dx[8] = {-1,0,1,0,-1,-1,1,1};
int dy[8] = {0,-1,0,1,-1,1,1,-1};
// 'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122
template<typename T>
T GCD(T u,T v){
    return v ? GCD(v,u%v) : u;
}
template<typename T>
T LCM(T x,T y){
    T gc = GCD(x,y);
    return x*y/gc;
}


int main(){
    int N; cin >> N;
    long long a[N+1];
    for (int i = 1; i <= N; i++){
        cin >> a[i];
    }
    long long L[N+2],R[N+2]; fill(L,L+N+2,0); fill(R,R+N+2,0);
    L[1] = a[1]; R[N] = a[N];
    for(int i = 2; i <= N; i++){
        L[i] = GCD(L[i-1],a[i]);
    }
    for(int i = N-1; i >= 1; i--){
        R[i] = GCD(R[i+1],a[i]);
    }
    long long ans = 0;
    for(int i = 1; i <= N; i++){
        long long tmp = GCD(L[i-1],R[i+1]);
        //cout << "L[i-1] = " << L[i-1] << ", R[i+1] = " << R[i+1] << endl;
        ans = max(ans, tmp);
    }
    cout << ans << endl;
}

Measured memory_bytes: 2560
import java.util.*;
import static java.lang.System.out;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long m = sc.nextLong();
        out.print(getValue(n) * getValue(m));
    }

    private static long getValue(long i){
        if(i==1){
            return 1;
        }else if(i ==2){
            return 0;
        }
        return i - 2;    }
}

Measured memory_bytes: 22996
#include<stdio.h>

int main()
{
    int x1,y1,x2,y2,m1,m2,x3,y3,x4,y4;
    scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
    m1= x1-x2;
    m2= y1-y2;
    x3=x2+m2;
    y3=y2-m1;
    x4=x1+m2;
    y4=y1-m1;
    printf("%d %d %d %d\n",x3,y3,x4,y4);
    return 0;
}


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

int main(){
  string str1, str2;
  int ans;
  cin >> str1; cin >> str2;
  for (int i=0; i<3; i++){
    if (str1[i]==str2[i])
      ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cmath>

int n, num;
double d;

int main(){
	
	scanf("%d", &n);
	d = (double)n / 1.08;
	if((int)(ceil(d) * 1.08) == n)
		printf("%.0lf\n", ceil(d));
	else
		puts(":(");
	
	return 0;
}

Measured memory_bytes: 128
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

A, B, C, X = map(int, read().decode("utf-8").split())

ans = 0
for a in range(A+1):
    for b in range(B+1):
        for c in range(C+1):
            sum_ = a * 500 + b * 100 + c * 50
            if sum_ == X:
                ans += 1
print(ans)

Measured memory_bytes: 9176
#include <iostream>
#include<algorithm>
#include<string>
#include<vector>
#define _USE_MATH_DEFINES
#include <math.h>
#include <iomanip>
#include <stdio.h>
#include <numeric>
#include <cmath>
#include <limits>
using namespace std;


int main()
{
	int w, a, b;
	cin >> w >> a >> b;
	cout << max(0,max(a - (b+w), b - (a + w))) << endl;
}





Measured memory_bytes: 256
import math
N = int(input())
n = 72

x = [None] * N
y = [None] * N
for i in range(N):
    x[i], y[i] = map(int, input().split())

ans = 0
for i in range(n):
    theta = (2 * math.pi / n) * i
    c = math.cos(theta)
    s = math.sin(theta)
    tmp_x = 0
    tmp_y = 0
    for j in range(N):
        if x[j] * c + y[j] * s > 0:
            tmp_x += x[j]
            tmp_y += y[j]
    if tmp_x**2 + tmp_y**2 > ans**2:
        ans = math.sqrt(tmp_x**2 + tmp_y**2)

print(ans)


Measured memory_bytes: 3188
mod = 10**9+7
N, K = map(int, input().split())
a = list(map(int, input().split()))
# dp[j] := the number of ways to distribute j candies
dp = [0] * (K+1)
dp[0] = 1
for i in range(N):
    ndp = [0] * (K+1)
    ndp[0] = 1
    for j in range(1, K+1):
        ndp[j] = ndp[j-1] + dp[j]
        if j - a[i] - 1 >= 0:
            ndp[j] -= dp[j-a[i]-1]
        ndp[j] %= mod
    dp = ndp
print(dp[K])

Measured memory_bytes: 66580
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <tuple>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;
 
int main(){
    ll h, w, k;
    cin >> h >> w >> k;

    vvl board(h, vl(w));  // board[i][j] : (i,j)にイチゴがあるとき1
    rep(i, h) {
        string s;
        cin >> s;
        rep(j, w) {
            if(s[j] == '#') {
                board[i][j] = 1;
            }
        }
    }

    vvl a(h, vl(w, -1));
    ll x = 1;  // ケーキにつける番号
    rep(i, h) {
        bool dame = true;  // i行目にイチゴがないならtrue
        rep(j, w) {
            if(board[i][j]) {
                dame = false;
            }
        }
        if(dame) {
            continue;
        }
        ll cnt = 0;
        rep(j, w) {
            if(board[i][j]) {
                if(cnt >= 1) {
                    x++;
                }
                cnt++;
            }
            a[i][j] = x;
        }
        x++;
    }

    rep(j, w) {
        ll y = -1;  // ケーキにつける番号
        rep(i, h) {
            if(a[i][j] > 0) {
                y = a[i][j];
            }
            else if(y > 0 && a[i][j] == -1) {
                a[i][j] = y;
            }
        }
    }

    rep(j, w) {
        ll y = -1;  // ケーキにつける番号
        for(ll i = h-1; i >= 0; i--) {
            if(a[i][j] > 0) {
                y = a[i][j];
            }
            else if(y > 0 && a[i][j] == -1) {
                a[i][j] = y;
            }
        }
    }
    
    rep(i, h) {
        rep(j, w) {
            cout << a[i][j];
            if(j < w-1) {
                cout << " ";
            }
        }
        cout << "\n";
    }

    re0;
}

Measured memory_bytes: 2176
char names[20][16];
int M[20][30],S[30],P[20];
main(n,m,i,j,d){
  for(;scanf("%d",&n),n;printf("%d %s\n",P[d],names[d])){
    memset(names,0,sizeof names),
    memset(M,0,sizeof M),
    memset(S,0,sizeof S),
    memset(P,0,sizeof P);
    for(i=0;i<n;i++)
      for(scanf("%s%d",names[i],&m),j=0;j<m;j++)scanf("%d",&d),M[i][d]++,S[d]++;
    for(i=0;i<n;i++)
      for(j=0;j<30;j++)
        if(M[i][j])P[i]+=1+n-S[j];
    for(d=0,m=999,i=0;i<n;i++)
      if(P[i]<m||(P[i]==m&&strcmp(names[i],names[d])<0))d=i,m=P[i];
  }
  exit(0);
}

Measured memory_bytes: 0