akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>

using namespace std;

#define FOR(i, x, y) for(int i = (x); i < (y); ++i)
#define REP(i, x, y) for(int i = (x); i <= (y); ++i)
#define PB push_back
#define MP make_pair
#define PH push
#define fst first
#define snd second
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int, int> pii;

ll n, ans = -1;

ll exgcd(ll a, ll b, ll &x, ll &y){
	if(!b){
		x = 1; y = 0;
		return a;
	}
	ll g = exgcd(b, a % b, y, x);
	y -= a / b * x;
	return g;
}

inline void solve(ll a, ll b){ // min x satisfying ax - by = 1, x, y \in \Z, a < b
	ll x, y, g = exgcd(a, b, x, y);
//	printf("a = %lld b = %lld x = %lld y = %lld\n", a, b, x, y);
	if(g != 1)
		return;
	// now we get ax + by = 1
	y = -y;
	b = -b;
	// now we get ax - by = 1
	if(y <= 0){
		ll k = (abs(y) + a / g) / (a / g);
		y += k * (a / g);
		x -= k * (b / g);
	}
	if(x <= 0)
		return;
	ll k = (x - 1) / (b / g);
	x += k * (b / g);
	y -= k * (a / g);
	if(log10(a) + log10(x) <= 18 && (ans == -1 || ans > a * x - 1))
		ans = a * x - 1;
	return;
}

int main(){
	scanf("%lld", &n);
	n <<= 1;
	for(ll a = 1; 1ll * a * a <= n; ++a) if(!(n % a)){
		ll b = n / a;
		solve(a, b);
		if(a != b)
			solve(b, a);
	}
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 4056
using System;
using System.IO;
using System.Collections.Generic;
using System.Linq;

namespace AtCoder.Contest.A
{
	static class Program
	{
		public static void Main(string[] args)
		{
			var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
			Console.SetOut(sw);

			var cin = new Scanner();

			string s = cin.Next();
			Console.WriteLine(s.Substring(0, 3));

			Console.Out.Flush();
		}
	}

	class Scanner
	{
		string[] s;
		int i;

		char[] cs = new char[] { ' ' };

		public Scanner()
		{
			s = new string[0];
			i = 0;
		}

		public string Next()
		{
			if (i < s.Length) return s[i++];
			string st = Console.ReadLine();
			while (st == "") st = Console.ReadLine();
			s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
			if (s.Length == 0) return Next();
			i = 0;
			return s[i++];
		}

		public int NextInt()
		{
			return int.Parse(Next());
		}

		public int[] ArrayInt(int N, int add = 0)
		{
			int[] Array = new int[N];
			for (int i = 0; i < N; i++)
			{
				Array[i] = NextInt() + add;
			}
			return Array;
		}

		public long NextLong()
		{
			return long.Parse(Next());
		}

		public long[] ArrayLong(int N, long add = 0)
		{
			long[] Array = new long[N];
			for (int i = 0; i < N; i++)
			{
				Array[i] = NextLong() + add;
			}
			return Array;
		}

		public double NextDouble()
		{
			return double.Parse(Next());
		}

		public double[] ArrayDouble(int N, double add = 0)
		{
			double[] Array = new double[N];
			for (int i = 0; i < N; i++)
			{
				Array[i] = NextDouble() + add;
			}
			return Array;
		}
	}
}

Measured memory_bytes: 25676
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REP2(i, a, b) for (int i = (a); i < (int)(b); i++)
typedef vector<int> VI;
typedef vector<VI> VVI;

int Main(int r)
{
    return r*r;
}

int main(void){
    int r;
    cin >> r;
    cout << Main(r) << endl;
    return 0;
}

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

int main(){
    int k, x; cin >> k >> x;
    if(500*k >= x) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int MAX_INT = 10000000;
int n, m;
int p, q, r;

int costMap[101][101];
int timeMap[101][101];
int visited[101];

class Node {
public:
	int cost, pos;
	Node(int p) {
		cost = 0;
		pos = p;
	}
	Node(int p, int c, const Node& pre) {
		cost = c + pre.cost;
		pos = p;
	}
	bool operator< (const Node& o) const {
		return cost > o.cost;
	}
};

int memo[101][101][2];

int main () {
	while (cin >> n >> m, n || m) {
		for (int i = 0; i <= m; i++) {
			fill(costMap[i], costMap[i] + m + 1, MAX_INT);
			fill(timeMap[i], timeMap[i] + m + 1, MAX_INT);
		}
		for (int i = 0; i < n; i++) {
			int a, b, cost, time;
			cin >> a >> b >> cost >> time;
			costMap[a][b] = costMap[b][a] = cost;
			timeMap[a][b] = timeMap[b][a] = time;
		}
		int k;
		for (int i = 0; i <= m; i++) {
			for (int j = 0; j <= m; j++) {
				memo[i][j][0] = 0x7fffffff;
				memo[i][j][1] = 0x7fffffff;
			}
		}
		for (cin >> k; k; k--) {
			cin >> p >> q >> r;
			if (memo[p][q][r] != 0x7fffffff) {
				cout << memo[p][q][r] << endl;
				continue;
			}
			fill(visited, visited + m + 1, MAX_INT);
			priority_queue<Node> que;
			que.push(Node(p));
			visited[p] = 0;
			while (!que.empty()) {
				Node current = que.top();
				que.pop();
				if (current.pos == q) {
					cout << current.cost << endl;
					memo[p][q][r] = memo[q][p][r] = current.cost;
					break;
				}
				for (int i = 1; i <= m; i++) {
					if (r) {
						if (timeMap[current.pos][i] != MAX_INT && timeMap[current.pos][i] + current.cost < visited[i]) {
							visited[i] = timeMap[current.pos][i] + current.cost;
							que.push(Node(i, timeMap[current.pos][i], current));
							//cout << current.pos << " to " << i << endl;
						}
					}
					else {
						if (costMap[current.pos][i] != MAX_INT && costMap[current.pos][i] + current.cost < visited[i]) {
							visited[i] = costMap[current.pos][i] + current.cost;
							que.push(Node(i, costMap[current.pos][i], current));
							//cout << current.pos << " to " << i << endl;
						}
					}
				}
			}
		}
	}
	return 0;
}

Measured memory_bytes: 0
#include<iostream>
using namespace std;
const int maxn=105;
int a[maxn][maxn];
int b[15];
int main(){
	int n;
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++)
			cin>>a[i][j];
	}
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>b[i];
		for(int j=0;j<3;j++){
			for(int k=0;k<3;k++){
				if(b[i]==a[j][k])
					a[j][k]=0;
			}	
		}
	}
	int flag=0;
	for(int i=0;i<3;i++){
		if(a[i][0]==0&&a[i][1]==0&&a[i][2]==0){
			flag=1;
			break;
		}
		if(a[0][i]==0&&a[1][i]==0&&a[2][i]==0){
			flag=1;
			break;
		}
	}
	for(int i=0;i<3;i++){
		if(a[i][0]==0&&a[i][1]==0&&a[i][2]==0){
			flag=1;
			break;
		}
		if(a[0][i]==0&&a[1][i]==0&&a[2][i]==0){
			flag=1;
			break;
		}
	}
	if(a[0][0]==0&&a[1][1]==0&&a[2][2]==0){
		flag=1;
	}
	if(a[2][0]==0&&a[1][1]==0&&a[0][2]==0){
		flag=1;
	}
	if(flag)
		cout<<"Yes";
	else
		cout<<"No";
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>



int main(){
    int i=0,y,g;
    char a[11],b[12];
    scanf("%s",a);
    scanf("%s",b);

    y = strlen(a);
    g = strlen(b);
    
    for(i;i<y;i++){

        if(a[i]!=b[i]){
            printf("No");
            return 0;
            break;}

       
    
    }

    if(i==y){
        if(g==y+1){
            printf("Yes");
        }
        else{printf("No");}
        
    }

    else{printf("No");}



return 0;

}

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

		cout<<(n/1000+1)*1000-n;
	}
	
	return 0;
}

Measured memory_bytes: 3632
//by yjz
#include<bits/stdc++.h>
using namespace std;
#define FF first
#define SS second
#define PB push_back
#define MP make_pair
#define foreach(it,s) for(__typeof((s).begin()) it=(s).begin();it!=(s).end();it++)
#ifndef LOCAL
#define cerr if(0)cout
#endif
typedef long long ll;
const int mod=1e9+7;
//My i/o stream
struct fastio
{
	char s[100000];
	int it, len;
	fastio() {it=len=0;}
	inline char get()
	{
		if (it<len) return s[it++]; it=0;
		len=fread(s, 1, 100000, stdin);
		if (len==0) return EOF; else return s[it++];
	}
	bool notend()
	{
		char c=get();
		while (c==' '||c=='\n') c=get();
		if (it>0) it--;
		return c!=EOF;
	}
}_buff;
#define geti(x) x=getnum()
#define getii(x,y) geti(x),geti(y)
#define getiii(x,y,z) getii(x,y),geti(z)
#define puti(x) putnum(x),putchar(' ')
#define putii(x,y) puti(x),puti(y)
#define putiii(x,y,z) putii(x,y),puti(z)
#define putsi(x) putnum(x),putchar('\n')
#define putsii(x,y) puti(x),putsi(y)
#define putsiii(x,y,z) putii(x,y),putsi(z)
inline ll getnum()
{
	ll r=0; bool ng=0; char c; c=_buff.get();
	while (c!='-'&&(c<'0'||c>'9')) c=_buff.get();
	if (c=='-') ng=1, c=_buff.get();
	while (c>='0'&&c<='9') r=r*10+c-'0', c=_buff.get();
	return ng?-r:r;
}
template <class T> inline void putnum(T x)
{
	if (x<0) putchar('-'), x=-x;
	register short a[20]={}, sz=0;
	while (x) a[sz++]=x%10, x/=10;
	if(sz==0) putchar('0');
	for (int i=sz-1; i>=0; i--) putchar('0'+a[i]);
}
inline char getreal() {char c=_buff.get(); while (c<=32) c=_buff.get(); return c;}
ll qpow(ll x, ll k) {return k==0? 1: 1ll*qpow(1ll*x*x%mod,k>>1)*(k&1?x:1)%mod;}
int n;
char g[311][611];
bool check(int d)
{
	for (int i=1; i<=n; i++)
	{
		for (int j=1; j<=n; j++)
		{
			if (g[i][j+d]!=g[j][i+d]) return false;
		}
	}
	return true;
}
int main()
{
	geti(n);
	for (int i=1; i<=n; i++)
	{
		for (int j=1; j<=n; j++)
		{
			g[i][j] = g[i][j+n] = getreal();
		}
	}
	int ans = 0;
	for (int i=0; i<n; i++) ans += check(i);
	cout<<ans*n<<endl;
	return 0;
}


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

// #define int long long
#define rep(i, n) for (long long i = (long long)(0); i < (long long)(n); ++i)
#define reps(i, n) for (long long i = (long long)(1); i <= (long long)(n); ++i)
#define rrep(i, n) for (long long i = ((long long)(n)-1); i >= 0; i--)
#define rreps(i, n) for (long long i = ((long long)(n)); i > 0; i--)
#define irep(i, m, n) for (long long i = (long long)(m); i < (long long)(n); ++i)
#define ireps(i, m, n) for (long long i = (long long)(m); i <= (long long)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) long long(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;
using vtp = vector<tuple<ll,ll,ll>>;
using vb = vector<bool>;

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

const ll INF = 1e9+10;
const ll MOD = 1e9+7;
const ll LINF = 1e18;

ll popcount(ll x){
  ll res=0;
  for(ll i=0; i<=40; i++){
    if(x>>i&1) res++;
  }
  return res;
}

ll f(ll x){
  if(x==0) return 0;
  ll cnt=popcount(x);
  return 1+f(x%cnt);
}

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  ll n; cin>>n;
  string s; cin>>s;
  
  ll cnt=0;
  rep(i,n) if(s[i]=='1') cnt++;
  
  ll f1=0, f2=0;
  vll t1(n+1,1), t2(n+1,1);
  // s%(mod popcount(s)+1), s%(mod popcount(s)-1) の前計算
  for(ll i=1; i<=n; i++){
    t1[i]=t1[i-1]*2%(cnt+1);
    if(cnt>1) t2[i]=t2[i-1]*2%(cnt-1);
  }
  
  for(ll i=0; i<n; i++){
    f1=f1*2+(s[i]=='1');
    f1%=(cnt+1);
    if(cnt>1){
      f2=f2*2+(s[i]=='1');
      f2%=(cnt-1);
    }
  }
  
for (int i = 0; i < n; i++) {
        if (s[i] == '1') {
            if (cnt == 1) puts("0");
            else {
                ll tmp = f2 - t2[n - 1 - i];
                tmp %= (cnt - 1);
                if (tmp < 0) tmp += cnt - 1;
                printf("%lld\n", f(tmp) + 1);
            }
        }
        else {
            ll tmp = f1 + t1[n - 1 - i];
            tmp %= (cnt + 1);
            printf("%lld\n", f(tmp) + 1);
        }
    }
  
}

Measured memory_bytes: 6776
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define vlli vector<ll>
#define vi vector<int>
#define vs vector<string>
#define vplli vector< pair< ll,ll> >
#define plli pair< ll,ll >
#define vps vector< pair< string, string> >
#define vpi vector< pair< int, int> >
#define all(x) x.begin(), x.end()
#define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define forn(i,n) for(ll i=0;i<n;i++)
#define print(arr,a,n) for(ll i=(a);i<(n);i++)cout<<(arr)[i]<<" ";
bool isp(string s){
 string ss = s;
  reverse(ss.begin(), ss.end());
  return (s == ss);
}
int main(){
    
       string s, a = "", b = "";
      cin >> s;
      int n = s.size(), i;
      for(i = 0; i < (n - 1)/2; i++){
        a+=s[i];
      }
      for(i = (n + 1)/2; i < n; i++){
        b+=s[i];
      }

      if(isp(a) && isp(b) && isp(s)){
        cout << "Yes" << endl;
      } else {
        cout << "No" << endl;
      }
    
}

Measured memory_bytes: 3620
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 = a+b;
    if(c<24){
      System.out.println(c);
    }else{
      System.out.println(c-24);
    }
  }
}

Measured memory_bytes: 21844
#include<stdio.h>
#include<string.h>
#define MAX 2000000
#define INFTY 10000000

int H,A[MAX+1];

void maxheap(int i){
  int left,right,saidai,x;
  left=2*i;
  right=2*i+1;

  if(left<=H && A[left] > A[i])
    saidai=left;
  else saidai=i;

  if(right<=H && A[right] > A[saidai])
    saidai=right;

  if(saidai!=i){
    x=A[i];
    A[i]=A[saidai];
    A[saidai]=x;
    maxheap(saidai);
  }
}

int extract(){
    int maxv;
    if(H<1)return -INFTY;
    maxv=A[1];
    A[1]=A[H--];
    maxheap(1);
    return maxv;
}

void increasekey(int i,int key){
    if(key<A[i])return;
    A[i]=key;
    while(i>1&&A[i/2]<A[i]){
        int t=A[i];
        A[i]=A[i/2];
        A[i/2]=t;
        i=i/2;
    }
}

void insert(int key){
    H++;
    A[H]=-INFTY;
    increasekey(H,key);
}

int main(){
    int key;
    char str[10];
    while(1){
    scanf("%s",str);
    if(str[0]=='e'&&str[1]=='n')break;
    if(str[0]=='i'){
        scanf("%d",&key);
        insert(key);
    }               
    else{
        printf("%d\n",extract());
    }
    }
    return 0;
}



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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(),v.end()
#define _GLIBCXX_DEBUG
int main() {
    int n,m;
    cin>>n>>m;
    cout<<(n*(n-1))/2+(m*(m-1))/2<<endl;

    return 0;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
A = []
B = []
for _ in range(N):
    A.append(list(input()))
for _ in range(M):
    B.append(list(input()))

for i in range(N - M + 1):
    for j in range(N - M + 1):
        # match
        flag = True
        for k in range(M):
            for l in range(M):
                if A[i + k][j + l] == B[k][l]:
                    pass
                else:
                    flag = False

        if flag:
            break

    if flag:
        break

if flag:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3064
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define REP(i,a,b) for (int i = a; i < (b); ++i)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define YY cout << "Yes" << endl;
#define NN cout << "No" << endl;
#define ve vector
#define pint pair<int,int>
const int INF = 1000000007;
const long double EPS = 1e-15;
const long double PI = acos(-1);
typedef long long ll;
using namespace std;
using Graph = vector<vector<int>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a,b); }
// *max_element(all(d))
int solve(){
  int n;
  cin >> n;
  vector<pint>v(n);
  rep(i,n){
    int a,b;
    cin >> a >> b;
    v[i] = {a,b};
  }
  sort(all(v));
  cout << v[n - 1].first + v[n - 1].second << endl;
  return 0; 
}
int main(){
  // ios::sync_with_stdio(false);cin.tie(nullptr);
  cout << fixed;cout << setprecision(16);
  solve();
  return 0;
}
//2 9,4 7,6 2

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

int main()
{
	int n;
	while (cin>>n){
		int counter = 0;
		for (int a = 0; a <= 9; a++){
			for (int b = 0; b <= 9; b++){
				for (int c = 0; c <= 9; c++){
					for (int d = 0; d <= 9; d++){
						if (a + b + c + d == n){
							counter++;
						}
					}
				}
			}
		}
		cout << counter << endl;
	}
	return 0;
}

Measured memory_bytes: 1160
io = STDIN
n,x=io.gets.split.map(&:to_i)
ar=io.gets.split.map(&:to_i)
if n==1
  puts (ar[0]-x).abs
else
  if ar.include? x
    p ar.each_cons(2).map {|a,b|b-a}.each_cons(2).map{|a,b|a.gcd b}.min
  else
    ar1 = ar.select{|a|a<x}+[x]+ar.select{|a|a>x}
    puts ar1.each_cons(2).map {|a,b|b-a}.each_cons(2).map{|a,b|a.gcd b}.min
  end
end


Measured memory_bytes: 14204
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N;
  string s,t;
  cin >> s >> t;
  int M = 0;
  for (int i = 1; i <= N; i++){
    if (s.substr(s.size() - i,i) == t.substr(0,i)) M = i;
  }
  cout << 2 * N - M;
}

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

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

N, M = map(int, raw_input().split())
cost = [0,2,5,5,4,5,6,3,7,6]
A = sorted(map(int, raw_input().split()))

DP = [0] + [-1] * N * 9
ans = [0, 0] * N

for i in range(1, N + 1):
    for j in A:
        pos = i - cost[j]
        if min(pos, DP[pos], DP[pos] + 1 - DP[i]) >= 0:
            DP[i], ans[i] = DP[pos] + 1, j

S, pos = "", N
while pos:
    S += str(ans[pos])
    pos -= cost[ans[pos]]

print S

Measured memory_bytes: 4216
while True:
    H,W=map(int,input().split())
    if H==0 & W==0:
        break

    for i in range(H):
        if i==0 or i==H-1:
            print('#'*W)
        else:
            c_W='.'*(W-2)
            print('#{}#'.format(c_W))

    print('')


Measured memory_bytes: 5616
#include <iostream>

using namespace std;

bool enough(long long int t, long long int hp[100000],long long int n, long long int a, long long int b){
	long long int attack_count = 0;
	for (long long int i=0; i<n; i++){
		long long int x = hp[i]-b*t;
		if (x>0){
			attack_count += (x+(a-b)-1)/(a-b);
			if (attack_count>t){
				return false;
			}
		}
	}
	
	return true;
}


int main(){
	long long int n,a,b;
	cin >> n >> a >> b;
	
	long long int hp[100000] = {};
	
	for(long long int i=0; i<n; i++){
		cin >> hp[i];
	}
	
	long long int left = 0;
	long long int right = 1000000000;
	long long int t;
	
	
	while (left!=right){
		t = (left + right)/2;
		if (enough(t, hp, n, a, b)){
			right = t;
		}else{
			left = t+1;
		}
	}
	
	cout << right << "\n";
	
	return 0;
}

Measured memory_bytes: 1024
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
using namespace std;
const int Maxn = 100010;
const int inf = 0x7fffffff;
struct node {
	int y, next, d;
}a[Maxn<<1]; int first[Maxn], len;
void ins(int x, int y, int d) {
	len++;
	a[len].y = y; a[len].d = d;
	a[len].next = first[x]; first[x] = len;
}
int n;
int d[Maxn];
struct lnode {
	int x, d;
	lnode(int x = 0, int d = 0) : x(x), d(d) {}
};
bool operator <(lnode A, lnode B) { return A.d > B.d; }
void dij() {
	priority_queue <lnode> q;
	for(int i = 0; i < n; i++) d[i] = inf;
	d[1] = 1;
	q.push(lnode(1, 1));
	while(!q.empty()){
		lnode x = q.top(); q.pop();
		if(d[x.x] < x.d) continue;
		for(int k = first[x.x]; k; k = a[k].next){
			int y = a[k].y;
			if(d[y] > d[x.x]+a[k].d){
				d[y] = d[x.x]+a[k].d;
				q.push(lnode(y, d[y]));
			}
		}
	}
}
int main() {
	int i, j, k;
	scanf("%d", &n);
	for(i = 0; i < n; i++){
		ins(i, (i+1)%n, 1);
		ins(i, i*10%n, 0);
	}
	dij();
	printf("%d\n", d[0]);
	return 0;
}

Measured memory_bytes: 3964
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define repv(i,a,b) for(ll i=b-1;i>=a;i--)
#define MAXN 200005
#define endl "\n"

ll power(ll x,ll y){ll res=1; while(y>0){if(y&1) res=res*x;y=y>>1;x=x*x;}return res;}

int n,arr[MAXN];
int maxx,maxx2,idx=-1;

int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n;
    for(int i=1;i<=n;i++) 
    {
        cin>>arr[i];
        if(arr[i]>maxx)
        {
            maxx2=maxx;
            maxx=arr[i];
            idx=i;
        }
    }
    for(int i=idx+1;i<=n;i++) maxx2=max(maxx2,arr[i]);
    for(int i=1;i<=n;i++)
    {
        if(i==idx) cout<<maxx2<<endl;
        else cout<<maxx<<endl;
    }
}

Measured memory_bytes: 2432
#include<stdio.h>
int main(void)
{
    int i,a=0,b=0;
    char s[3];
        scanf("%s",s);
    for(i=0;i<3;i++){
        if(s[i]=='A') a++;
        if(s[i]=='B') b++;
    }
    if(a==3 || b==3){
        printf("No\n");
    } else {
        printf("Yes\n");
    }
    return 0;
}

Measured memory_bytes: 128
//                                      KiSmAt
#include "bits/stdc++.h"
using namespace std;
 
using ll = long long;
 
const ll inf = 1e18;
const int N = 2 * 1e5 + 10;

ll res;
ll a[N], vis[N];

vector<ll> v[N];

ll Dfs(ll node){
    vis[node] = 1;
    for(auto i: v[node]){
        if(!vis[i]) Dfs(i);  
        a[node] = max(a[node], 1 + a[i]);
    }
    return a[node];
}

void solve(){
    ll n, m, x, y;
    cin >> n >> m;
    for(int i = 0; i < m; ++i){
        cin >> x >> y;
        v[x].emplace_back(y);
    }
    for(int i = 1; i <= n; ++i){
        if(!vis[i]){
            res = max(res, Dfs(i));
        }
    }
    cout << res;
}
 
int main(int argc, char const *argv[]){
    ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
    ll t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}
// nEro

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

#define Int register int
#define mod 998244353
#define MAXN 10005 

template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}

char s1[MAXN],s2[MAXN]; 
int n,f[MAXN][MAXN],fac[MAXN],ifac[MAXN];

int mul (int a,int b){return 1ll * a * b % mod;}
int add (int a,int b){return a + b >= mod ? a + b - mod : a + b;}
int qkpow (int a,int b){int res = 1;for (;b;b >>= 1,a = 1ll * a * a % mod) if (b & 1) res = 1ll * res * a % mod;return res;}
int binom (int a,int b){return 1ll * fac[a] * ifac[b] % mod * ifac[a - b] % mod;}

signed main(){
	scanf ("%s%s",s1 + 1,s2 + 1),n = strlen (s1 + 1);
	fac[0] = 1;for (Int i = 1;i <= n;++ i) fac[i] = 1ll * fac[i - 1] * i % mod;
	ifac[n] = qkpow (fac[n],mod - 2);for (Int i = n;i;-- i) ifac[i - 1] = 1ll * ifac[i] * i % mod;
	int sum1 = 0,sum2 = 0;//sum1表示可以传递的中间节点个数，sum2表示可以作为链头的个数 
	for (Int i = 1;i <= n;++ i) if (s1[i] == '1' && s2[i] == '1') ++ sum1;else if (s1[i] > s2[i]) ++ sum2;
	f[0][0] = 1;
	for (Int i = 0;i <= sum1;++ i)
		for (Int j = 0,cur;j <= sum2;++ j){
			if (!(cur = f[i][j])) continue;
			f[i + 1][j] = add (f[i + 1][j],mul (cur,mul (i + 1,j)));
			f[i][j + 1] = add (f[i][j + 1],mul (cur,mul (j + 1,j + 1)));
		}
	int ans = 0;
	for (Int i = 0;i <= sum1;++ i) ans = add (ans,mul (binom (sum1 + sum2,i),mul (binom (sum1,i),mul (fac[i],mul (fac[i],f[sum1 - i][sum2])))));
	write (ans),putchar ('\n');
	return 0;
}

Measured memory_bytes: 73988
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) (v).begin(),(v).end()
#define out(a) cout << (a) << endl
using namespace std;
using ll = long long;
int main(){
    int a, b;
    cin >> a >> b;
    int mini = max(a/0.08, b/0.1);
    int maxi = min((a+1)/0.08-1, (b+1)/0.1-1);
    for (int i=mini; i<=maxi; i++){
        int x = i * 0.08;
        int y = i * 0.1;
        if(x == a && y == b){
            out(i);
            return 0;
        }
    }
    out(-1);
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
int main(){
    int a;
    while(cin>>a){
        vector<vector<int>> dp(a,vector<int> (3,0));
        vector<vector<int>> num(a,vector<int> (3,0));
        for(int i=0;i<a;i++){
            for(int j=0;j<3;j++){
                cin>>num[i][j];
            }
        }
        dp[0][0]=num[0][0];
        dp[0][1]=num[0][1];
        dp[0][2]=num[0][2];
        for(int i=1;i<a;i++){
            for(int j=0;j<3;j++){
                if(j==0){
                    dp[i][j]=max(dp[i-1][1]+num[i][0],dp[i-1][2]+num[i][0]);
                }
                else if(j==1){
                    dp[i][j]=max(dp[i-1][0]+num[i][1],dp[i-1][2]+num[i][1]);
                }
                else if(j==2){
                    dp[i][j]=max(dp[i-1][0]+num[i][2],dp[i-1][1]+num[i][2]);
                }
            }
        }
        int t=max(dp[a-1][0],dp[a-1][1]);
        cout<<max(t,dp[a-1][2])<<endl;
    }
}


Measured memory_bytes: 14352
import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int x = sc.nextInt();
    int[] m = new int[n];
    int count = 0;
    int min = (int)Math.pow(10, 5);
    for (int i = 0; i < n; i++) {
      m[i] = sc.nextInt();
      x = x - m[i];
      count++;
      if (m[i] < min) {
        min = m[i];
      }
    }
    count = count + x / min;
    System.out.println(count);
  }
}

Measured memory_bytes: 35944
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
using ll = long long;

int n;
ll C;
ll ans = 0;
const int maxn = 1e5 + 10;
const ll oo = 0x3f3f3f3f3f3f3f3f;

struct Point{
	ll x;
	int v;
};

Point p[maxn];
ll sum[maxn];

bool cmp(Point p1 , Point p2){
	return p1.x < p2.x;
}

void solve(){
	sort(p + 1 , p + n + 1 , cmp); 
	sum[0] = 0;
	ll cur = 0 , mx = 0; 
	for(int i = 1 ; i <= n ; ++ i){
		cur += p[i].v - (p[i].x - p[i - 1].x);
		if(cur > mx) mx = cur;
		sum[i] = mx;
	}
	ans = max(ans , sum[n]);
	ll now = 0;
	for(int i = n ; i >= 1 ; -- i){
		now += p[i].v;
		ans = max(ans , sum[i - 1] - 2 * (C - p[i].x) + now);
	} 
}

int main(){
	ios::sync_with_stdio(0);
	cin >> n >> C;	
	for(int i = 1 ; i <= n ; ++ i)
		cin >> p[i].x >> p[i].v;
	solve();
	for(int i = 1 ; i <= n ; ++ i)
		p[i].x = C - p[i].x;
	solve();
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 2688
sx, sy, tx, ty = map(int, input().split())

ans = ""
y_len = ty-sy
x_len = tx-sx

for _ in range(y_len):
    ans = ans+"U"

for _ in range(x_len):
    ans = ans+"R"

for _ in range(y_len):
    ans = ans+"D"

for _ in range(x_len):
    ans = ans+"L"

ans = ans+"L"

for _ in range(y_len+1):
    ans = ans+"U"

for _ in range(x_len+1):
    ans = ans+"R"

ans = ans+"D"
ans = ans+"R"

for _ in range(y_len+1):
    ans = ans+"D"

for _ in range(x_len+1):
    ans = ans+"L"

ans = ans+"U"
print(ans)


Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
#include <set>
#include <map>

using namespace std;

int main(void){
    long long n, a[100005];
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    sort(a,a+n);
    long long max[2], cnt=0;
    max[0] = a[n-1];
    for(int i=n-2; i>=0; i--){
        if(max[cnt] == a[i]){
            max[cnt] = a[i];
            cnt++;
        }else{
            max[cnt] = a[i];
        }
        if(cnt == 2){
            break;
        }
    }
    if(cnt < 2){
        cout << "0" << endl;
    }else{
        cout << max[0] * max[1] << endl;
    }

    return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
double v[60];
int main()
{
	int n;
	cin >> n;
	for (int i = 0;i < n;i++)
	{
		cin >> v[i];
	}
	sort(v,v + n);
	for (int i = 1;i < n;i++)
	{
		v[i] = (v[i - 1] + v[i]) / 2;
	}
	printf("%.6f\n",v[n - 1]);
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
typedef long long ll;
int main(void){
    int n,a[100000];
    ll s=0,m,k=1e9+7,l=0;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        s+=a[i];
        k=min(k, (ll)a[i]);
    }
    m=(ll)n*(n+1)/2;
    if(s%m>0){
        cout<<"NO"<<endl;
        return 0;
    }else{
        s=s/m;
        for(int i=0;i<n;i++){
            if(a[i]>=a[(i+1)%n]){
                ll y=(a[i]-a[(i+1)%n]+s);
                if(y%n==0){
                    l+=y/n;
                }else{
                    cout<<"NO"<<endl;
                    return 0;
                }
            }
        }
        if(l==s){
            cout<<"YES"<<endl;
        }else{
            cout<<"NO"<<endl;
            return 0;
        }
    }
    
}


Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

const int MOD = 1e+9 + 7;

template <typename T>
T pow_mod( T n, T p )  // n^p % m
{
    if( p == 0 ) return 1;
    if( p%2 == 1 ) return pow_mod(n, p-1) * n % MOD;
    else{
        T tmp = pow_mod(n, p/2) % MOD;
        return tmp*tmp % MOD;
    }
}

int main()
{
    int n;
    cin >> n;
    vector<int> a(n+1);
    REP(i, n+1) cin >> a[i];

    int duplicate;
    vector<int> num_appeared(n+1, 0);
    REP(i, n+1){
        ++num_appeared[a[i]];
        if(num_appeared[a[i]] == 2) duplicate = a[i];
    }

    int l = 1e+9, r = 0; // l, r: 同じ数字が現れる位置 (l < r)
    REP(i, n+1){
        if(a[i] == duplicate){
            l = min(l, i);
            r = max(r, i);
        }
    }

    int m = l + n-r;
    vector<long long> mCk(m+1);
    mCk[0] = 1;
    FOR(i, 1, m+1){
        mCk[i] = mCk[i-1];
        mCk[i] *= (m-i+1)*pow_mod<long long>(i, MOD-2) % MOD;
        mCk[i] %= MOD;
    }

    long long ans = 1;
    FOR(i, 1, n+2){ // i 枚取るとき
        ans *= (n+1-(i-1)) * pow_mod<long long>(i, MOD-2) % MOD;
        ans %= MOD;
        if(m < i-1) cout << ans << endl;
        else{
            cout << (ans-mCk[i-1]+MOD)%MOD << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 2816
n = gets.to_i
s = gets.chomp.split("")
choices = [["S", "S"], ["S", "W"], ["W", "S"], ["W", "W"]]
choices.each_with_index do |choice|
  until choice.size == n
    tmp = choice[-2, 2]
    if (tmp.uniq.size == 1 && s[choice.size - 1] == "o") || (tmp.uniq.size == 2 && s[choice.size - 1] == "x")
      choice << "S"
    else
      choice << "W"
    end
  end
  last_surrounded_same = (choice.last == "S" && s.last == "o") || (choice.last == "W" && s.last == "x")
  last_correct = (last_surrounded_same && choice[-2] == choice[0]) || (!last_surrounded_same && choice[-2] != choice[0])
  first_surrounded_same = (choice.first == "S" && s.first == "o") || (choice.first == "W" && s.first == "x")
  first_correct = (first_surrounded_same && choice[-1] == choice[1]) || (!first_surrounded_same && choice[-1] != choice[1])
  if last_correct && first_correct
    puts choice.join
    exit
  end
end
puts -1


Measured memory_bytes: 45688
#include <bits/stdc++.h>
using namespace std;using ll=long long;using uint=unsigned int;using pii=pair<int,int>;using pll=pair<ll,ll>;using ull = unsigned long long;using ld=long double;template<typename T>void _(const char*s,T h){cerr<<s<<" = "<<h<<"\n";}template<typename T,typename...Ts>void _(const char*s,T h,Ts...t){int b=0;while(((b+=*s=='(')-=*s==')')!=0||*s!=',')cerr<<*s++;cerr<<" = "<<h<<",";_(s+1,t...);}// break continue pop_back 998244353
#define int ll
#define pii pll
#define f first
#define s second
#define pb emplace_back
#define forn(i,n) for(int i=0;i<(n);++i)
#define sz(a)((int)(a).size())
#define sqr(x) ((x)*(x))
struct init{init(){cin.tie(0);iostream::sync_with_stdio(0);cout<<fixed<<setprecision(10);cerr<<fixed<<setprecision(5);}~init(){
#ifdef LOCAL
#define dbg(...) _(#__VA_ARGS__,__VA_ARGS__)
cerr<<"Time elapsed: "<<(double)clock()/CLOCKS_PER_SEC<<"s.\n";
#else
#define dbg(...) 
#endif
}}init;template<typename T,typename U>void upx(T&x,U y){if(x<y)x=y;}template<typename T,typename U>void upn(T&x,U y){if(x>y)x=y;}
const int N=2e5+5;
pii a[N];
vector<int> dp[N];
int32_t main(){
    vector<int> zs;
    int nn,T,n=0;
    cin>>nn>>T;
    forn(i,nn){
        int x,y;
        cin>>x>>y;
        if(x)a[n++]={x,y};
        else zs.pb(y);
    }
    sort(a,a+n,[](const pii&p1,const pii&p2){
        return p2.f*(p1.s+1)<p1.f*(p2.s+1);
    });
    sort(zs.begin(), zs.end());
    dp[0]={0};
    forn(i,n){
        dp[i+1]=dp[i];
        dp[i+1].pb(T+1);
        forn(j,sz(dp[i])){
            upn(dp[i+1][j+1],dp[i][j]+1+a[i].f*(dp[i][j]+1)+a[i].s);
        }
        if(dp[i+1].back()>T)dp[i+1].pop_back();
    }
    int ans=0;
    forn(j,sz(dp[n])){
        if(dp[n][j]<=T){
            int r=dp[n][j],pot=j;
            for(int i:zs){
                if(r+i+1<=T){
                    r+=i+1;
                    pot++;
                }else{
                    break;
                }
            }
            upx(ans,pot);
        }
    }
    cout<<ans<<'\n';
    return 0;
}


Measured memory_bytes: 105052
#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>
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)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

int main(){
  int n;
  cin >> n;
  int b[n+1];
  int ans[n+1]={};
  b[0]=0;
  rep(i,n)cin >> b[i+1];
  for(int i=n;i>=1;i--){
   if(b[i]>i){
     cout << -1 << endl;
     return 0;
   }
  }
  bool used[n+1];
  rep(i,n+1)used[i]=false;
  for(int i=n;i>=1;i--){
    int cnt=1;
    int temp=1;
    while(cnt<b[i]){
      if(!used[temp])cnt++;
      temp++;
    }
    while(used[temp])temp++;
    used[temp]=true;
    ans[temp]=b[i];
  }
  for(int i=1;i<=n;i++)cout << ans[i] << endl;
return 0;}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template <class T> ll size(const T &x) { return x.size(); }
#define rep(i,a,b) for(ll i = (a); i < (b); ++i)
#define iter(it,c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end();++it)
#define MOD 1000000007
#define pb push_back
#define fs first
#define sc second
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;

const int INF = 2147493647;
const double pi = acos(-1);
const double EPS = 1e-9;

int main()
{
    ll n;
    cin >> n;
    vi A(n);
    vi B(n);
    vi C(n);
    rep(i,0,n) cin >> A[i];
    rep(i,0,n) cin >> B[i];
    rep(i,0,n-1) cin >> C[i];
    ll sm = B[A[0]-1];
    rep(i,1,n){
        sm += B[A[i]-1];
        if(A[i]-1 == A[i-1]) sm += C[A[i-1]-1];
    }
    cout << sm  << endl;

}


Measured memory_bytes: 256
n,k=map(int,input().split())
l=sorted(map(int,input().split()))
def gcd(x,y):
  if y==0:return x
  return gcd(y,x%y)
ans=""
s=0
for i in l:
  s=gcd(i,s)
  if s==1:break
else:
  if k%s!=l[-1]%s:
    ans="IM"
if l[-1]<k:ans="IM"
print(ans+"POSSIBLE")


Measured memory_bytes: 14108
//Never stop trying
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef string str;
typedef long long ll;
#define int ll
typedef double db;
typedef long double ld;

typedef pair<int,int> pi;
#define fi first
#define se second

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<str> vs;
typedef vector<pi> vpi;

#define pb push_back
#define eb emplace_back
#define pf push_front

#define lb lower_bound
#define ub upper_bound

#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define endl "\n"

const int MOD = 1e9+7; //998244353
const ll INF = 1e18;
const int nx[4]={0,0,1,-1}, ny[4]={1,-1,0,0}; //right left down up

void IO(){
#ifndef ONLINE_JUDGE 
    freopen("in.txt", "r", stdin); 
    freopen("out.txt", "w", stdout); 
#endif 
}

const int MX=1e5;
int N;
int a[MX],b[MX],c[MX];
int memo[MX][4];

int solve(int idx, int l){
	if(idx==N) return 0;
	if(memo[idx][l]!=-1) return memo[idx][l];
	int ans=-INF;
	if(l!=1) ans=max(ans,solve(idx+1,1)+a[idx]);
	if(l!=2) ans=max(ans,solve(idx+1,2)+b[idx]);
	if(l!=3) ans=max(ans,solve(idx+1,3)+c[idx]);
	return memo[idx][l]=ans;
}

int32_t main(){
   boost;
   IO();
   memset(memo,-1,sizeof(memo));
   cin>>N;
   for(int i=0; i<N; i++) cin>>a[i]>>b[i]>>c[i];
   cout << solve(0,0) << endl;

   return 0;
}



Measured memory_bytes: 13744
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define str to_string
#define endl "\n"
#define PI 3.141592653589
using namespace std;
using lint = long long;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}

set<lint> lun;
void lunmake(string x,int depth,int last){
    if(depth>0){
        for(int i=max(last-1,0);i<=min(last+1,9);i++){
            lun.insert(stoll(x+str(i)));
            lunmake(x+str(i),depth-1,i);
        }
    }
}

//AC(*'ω'*)AC(*'ω'*)AC(*'ω'*)AC(*'ω'*)AC(*'ω'*)AC(*'ω'*)AC
int main(){
    int n;cin>>n;
    for(int i=1;i<10;i++){
        lun.insert(i);
        lunmake(str(i),10,i);
    }
    for(auto x:lun){
        n--;
        if(n==0)cout<<x<<endl;
    }
}


Measured memory_bytes: 30908
#include<bits/stdc++.h>
#define mo 1000000007
#define pi 3.1415926535898 
using namespace std;
long long read(){
    long long xx=0,flagg=1;
    char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')
        ch=getchar();
    if(ch=='-'){
        flagg=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        xx=xx*10+ch-'0';
        ch=getchar();
    }
    return xx*flagg;
}
void pus(long long xx,long long flagg){
    if(xx<0){
        putchar('-');
        xx=-xx;
    }
    if(xx>=10)
        pus(xx/10,0);
    putchar(xx%10+'0');
    if(flagg==1)
        putchar(' ');
    if(flagg==2)
        putchar('\n');
    return;
}
long long n,m,i,a[100005],book[100005],sum,sum2,max1;
char s[100005];
int main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
   	cin>>n>>a[1];
   	s[1]='+';
   	for(i=2;i<=n;i++)
   		cin>>s[i]>>a[i];
   	for(i=1;i<=n;i++)
   		if(s[i]=='+')
   			book[i]=book[i-1]+a[i];
   		else
   			book[i]=book[i-1]-a[i];
   	max1=book[n];
   	for(i=n;i>=1;i--){
		sum2+=a[i];
		if(s[i]=='-'){
			max1=max(max1,book[i-1]-sum2+sum);
			sum+=sum2;
			sum2=0;
		}
	}
	pus(max1,2);
    return 0;
}

Measured memory_bytes: 1920
#include<bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;
#define F first
#define S second
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long 
#define ld long double
#define pii pair <int ,int >
#define bug(x)  cout<<"passed "<<x<<endl;
long long const inf = 1e18, linf = 2e9, mod = 1e9+7;
int const mxn = 4e5+10;
 
ll poww(ll a, ll b, ll md) {
    return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));
}




int main(){
	long double  l ; 
	cin>>l;
	cout<<setprecision(10)<<fixed<<(l/3)*(l/3)*(l/3);
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <map>
#include <cmath>
#include <bitset>
#include <string>
#include <queue>

using namespace std;

#define int long long

signed main() {
    int n;
    cin >> n;
    vector<int> v(n, 0);
    for(int i = 0; i < n - 1; i++) {
        int m;
        cin >> m;
        v[m - 1]++;
    }

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

Measured memory_bytes: 4780
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<queue>
#include<string>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 1e4+5;

int main(){
	char s[maxn]; cin >> s+1;
	int sum = 0, len = strlen(s+1);
	for(int i = 1; i <= len/2; i++){
		if(s[i] != s[len-i+1]) sum++;
	}
	cout << sum;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(n) begin(n), end(n)
using ll = long long;
using namespace std;

int main(){
	string n;
	cin >> n;
	int ans, a1 = 0, a2 = 0;
	rep(i, n.size()){
		a1 += n[i] - '0';
	}
	rep(i, n.size()){
		if(i == 0) a2 += n[i] - '0' - 1;
		else a2 += 9;
	}
	// cerr << a1 << " " << a2 << endl;
	ans = max(a1, a2);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<set>
#include<utility>
#include<typeinfo>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef set<int> S;
#define rep(i, n) for(int i=0; i<n; i++)
const ll MOD=1e9+7;

int main(){

	int n, i;
	cin >> n >> i;
	cout << n-i+1 << endl;

	return 0;
}

Measured memory_bytes: 256
N, = map(int, input().split())
ACTIVITIES = list(map(int, input().split()) for _ in range(N))

DP = [[0] * 3 for _ in range(N+1)]

for i in range(0, N):
    for j, value in enumerate(ACTIVITIES[i]):
        DP[i+1][j] = max(DP[i][k] if j != k else 0 for k in range(3)) + value

print(max(DP[N]))


Measured memory_bytes: 94424
#include <bits/stdc++.h> 
using namespace std;
#define rep(i, N) for(int i=0; i<N; i++)
typedef long long ll;
#define dump(x) cerr<<#x<<"="<<x<<endl

int main() {
    int n, m; cin >> n >> m;
    vector<int> x(m);
    priority_queue<int> que;
    rep(i, m) cin >> x.at(i);

    if(n>=m) {
        cout << 0 << endl;
        return 0;
    }

    sort(x.begin(), x.end());
    rep(i, m-1){
        que.push(x.at(i+1) - x.at(i)); 
    }

    for(int i=0; i<n-1; i++){
       int tmp = 0;
       tmp = que.top(); 
       que.pop();
       que.push(0);
    }

    ll sum = 0;
    while(!que.empty()){
        sum += que.top();
        que.pop();
    }

    cout << sum << endl;

}

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


#define li          long long int
#define rep(i,to)   for(li i=0;i<((li)(to));i++)
#define repp(i,start,to)    for(li i=(li)(start);i<((li)(to));i++)
#define pb          push_back
#define sz(v)       ((li)(v).size())
#define bgn(v)      ((v).begin())
#define eend(v)     ((v).end())
#define allof(v)    (v).begin(), (v).end()
#define dodp(v,n)       memset(v,(li)n,sizeof(v))
#define bit(n)      (1ll<<(li)(n))
#define mp(a,b)     make_pair(a,b)
#define rin rep(i,n)
#define EPS 1e-12
#define ETOL 1e-8
#define MOD 1000000007
typedef pair<li, li> PI;

#define INF bit(60)

#define DBGP 1


#define idp if(DBGP)
#define F first
#define S second
#define p2(a,b)     idp cout<<a<<"\t"<<b<<endl
#define p3(a,b,c)       idp cout<<a<<"\t"<<b<<"\t"<<c<<endl
#define p4(a,b,c,d)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<endl
#define p5(a,b,c,d,e)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<endl
#define p6(a,b,c,d,e,f)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<endl
#define p7(a,b,c,d,e,f,g)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<endl
#define p8(a,b,c,d,e,f,g,h)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<endl
#define p9(a,b,c,d,e,f,g,h,i)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<endl
#define p10(a,b,c,d,e,f,g,h,i,j)        idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<"\t"<<j<<endl
#define foreach(it,v)   for(__typeof((v).begin()) it=(v).begin(); it!=(v).end(); ++it)
#define p2p(x)      idp p2((x).F, (x).S)
#define dump(x,n)   idp{rep(i,n){cout<<x[i]<<" ";}puts("");}
#define dump2(x,n)  idp{rep(i,n){cout<<"["<<x[i].F<<" , "<<x[i].S<<"] ";}puts("");}
#define dumpi(x)    idp{foreach(it, x){cout<<(*it)<<" ";}puts("");}
#define dumpi2(x)   idp{foreach(it, x){cout<<"["<<(it)->F<<" , "<<(it)->S<<"] ";}puts("");}

#define read2d(a,w,h)   rep(i,h)rep(j,w)cin>>a[i][j]
#define dump2d(a,w,h)   rep(i,h){rep(j,w)cout<<a[i][j]<<" ";puts("");}

typedef pair<li, li> PI;

li h[1010];

int main() {
    li n;
    cin >> n;
    li t, a;
    cin >> t >> a;
    li res = -1;
    li diff = INF;
    rin{
        cin >> h[i];
        if (abs(1000 * t - 6 * h[i] - a * 1000) < diff) {
            diff = abs(1000 * t - 6 * h[i] - a * 1000);
            res = i;
        }
    }
    cout << res + 1 << endl;

    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
int n,d,ans;
double w(long long x,long long y)
{
	return (double)sqrt((long long)(x*x)+(long long)(y*y));
}
int main()
{
	scanf("%d%d",&n,&d);
	for(int i=1;i<=n;i++)
	{
		long long x,y;
		scanf("%lld%lld",&x,&y);
		if(w(x,y)<=(double)(d)) ans++;
	}
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 3804
N,Q = map(int,input().split())
S = (input())

lr = []

for i in range(Q):
    lr.append(list(map(int,input().split())))

acs = [0]*(N+1)
tmp = 0
for i in range(N-1):
    if S[i] =="A" and S[i+1] =="C":
        tmp = 1
    else:
        tmp = 0
    acs[i+1] = acs[i] + tmp
    

for i in range(Q):
    print(acs[lr[i][1]-1]-acs[lr[i][0]-1])

Measured memory_bytes: 32196
import java.util.Scanner;

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

        while (sc.hasNext()) {
            str = sc.next();
            for(int i = 0; i < str.length(); i++) {
                c = str.charAt(i);
                if (c >= 'A' && c <= 'z') {
                    if (c >= 'a' && c <= 'z') {
                        System.out.print((char)(c + 'A' - 'a'));
                    } else {
                        System.out.print((char)(c + 'a' - 'A'));
                    }
                } else {
                    System.out.print(c);
                }
            }
            if (sc.hasNext())
                System.out.print(" ");
        }
        System.out.println();
    }
}


Measured memory_bytes: 27160
#include <iostream>
using namespace std;
int gcd(int a,int b)
{
    return b==0?a:(gcd(b,a%b));
}
int main()
{
    int k,sum=0;
    cin>>k;
    for(int i=1;i<=k;i++)
        for(int j=1;j<=k;j++)
        for(int g=1;g<=k;g++)
    {
        if(i!=j&&i!=g&&j!=g)
        {
            sum+=gcd(i,gcd(j,g));
        }
        else if((i==j&&j!=g)||(i==g&&j!=g)||(j==g&&j!=i))
        {
            sum+=gcd(i,gcd(j,g));
        }
        else
        {
            sum+=i;
        }
    }
    cout<<sum;
    return 0;
}




Measured memory_bytes: 3228
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		String S = sc.next();
		String T = sc.next();
		char[] sArray = S.toCharArray();
		char[] tArray = T.toCharArray();
		int count = 0;
		for (int i = 0; i < sArray.length; i++) {
			if (sArray[i] == tArray[i]) {
				count++;
			}
		}
		System.out.println(count);
		sc.close();
	}
}

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

using namespace std;

typedef long long ll;

int main(void) {
  ll n;
  cin >> n;
  ll ans = 1;
  ll cnt = (ll)(pow(10, 9) + 7);
  for (ll i = 1; i <= n; i++) {
    ans *= i;
    ans %= cnt;
  }
  cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
import bisect

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

a.sort()
b.sort()
c.sort()
# print(a,b,c)

ans = 0
for p in b:
    t = bisect.bisect_left(a,p)
    b = n - bisect.bisect_left(c,p+1)
    # print(t, b)
    ans += t * b

print(ans)

Measured memory_bytes: 23360