akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <ctime>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <numeric>
#include <cassert>
using namespace std;
static const double EPS = 1e-10;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define all(a) a.begin(),a.end()
#define mp(a,b,c) make_pair(make_pair(a,b),c)
#define pb(a) push_back(a)
#define SS stringstream
#define DBG1(a) rep(_X,sz(a)){printf("%d ",a[_X]);}puts("");
#define DBG2(a) rep(_X,sz(a)){rep(_Y,sz(a[_X]))printf("%d ",a[_X][_Y]);puts("");}
#define bitcount(b) __builtin_popcount(b)
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)

#define delete(a,n) a.erase(remove(all(a),n),a.end())
template<typename T, typename S> vector<T>& operator<<(vector<T>& a, S b) { a.push_back(b); return a; }
template<typename T> void operator>>(vector<T>& a, int b) {while(b--)if(!a.empty())a.pop_back();}
bool isprime(int n){ if(n<2)return false;  for(int i=2;i*i<=n;i++)if(n%i==0)return false;  return true;} 
ll b_pow(ll x,ll n){return n ? b_pow(x*x,n/2)*(n%2?x:1) : 1ll;}
string itos(int n){stringstream ss;ss << n;return ss.str();}

int x,y,z;
long long a[3];

vector<long long> getDivisor(long long n){
	vector<long long> ret;
	for(long long i=1;i*i<=n;i++){
		if(n % i==0){
			ret.push_back(n/i);
			if(i != n/i)ret.push_back(i);
		}
	}
	sort(ret.begin(),ret.end());
	return ret;
}

int main(){
	int n;
	cin >> n;
	for(int i = 0 ; i < n ; i++) cin >> a[i];
	long long g = a[0];
	for(int i = 1 ; i < n ; i++){
		g = __gcd(g,a[i]);
	}
	vector<long long> x = getDivisor(g);
	for(int i = 0 ; i < x.size() ; i++)
		cout << x[i] << endl;
}

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

int main() {
	int n,m;
	cin>>n>>m;
	int x[n];
	for(int i=0;i<n;i++){
		x[i]=1000000001;
	}
	int flag=1;
	int l[m],r[m],d[m];
//	int g[n][n];
	vector<vector<pair<int,int>>> g(n,vector<pair<int,int>>(1,make_pair(0,0)));
	int used[n];
	for(int i=0;i<n;i++){
		used[i]=0;
	}
	for(int i=0;i<m;i++){
		cin>>l[i]>>r[i]>>d[i];
		used[l[i]-1]=1;
		used[r[i]-1]=1;
		g[l[i]-1].push_back(make_pair(r[i]-1,d[i]));
		g[r[i]-1].push_back(make_pair(l[i]-1,-d[i]));
	}
	int i=0;
	vector<int> s;
	while(i<n){
		if(used[i]){
			used[i]=0;
			x[i]=0;
			s={i};
		}
		while(s.size()){
			int p=s.back();
			s.pop_back();
//			cout<<'p'<<p<<endl;
			while(g[p].size()){
				int nextp=g[p].back().first;
				int nextx=g[p].back().second+x[p];
				g[p].pop_back();
				if(nextx!=x[p]){
//					cout<<"nextp"<<nextp<<"nextx"<<nextx<<endl;
					if(used[nextp]){
						used[nextp]=0;
						x[nextp]=nextx;
						s.push_back(nextp);
					}else{
						if(x[nextp]!=nextx){
							cout<<"No"<<endl;
							return 0;
						}
					}
				}
			}

		}
		i++;
	}
	if(flag){
		cout<<"Yes"<<endl;
	}else{
		cout<<"No"<<endl;
	}



	return 0;
}

Measured memory_bytes: 13940
n, m = [int(i) for i in input().split()]

ll = []
rr = []
for i in range(m):
    l, r = [int(i) for i in input().split()]
    ll.append(l)
    rr.append(r)

ans = min(rr) - max(ll) + 1
if ans < 0:
    ans = 0
print(ans)

Measured memory_bytes: 10996
// ABC F
#include<bits/stdc++.h>
#define mo 1000000007
using namespace std;
long long n,i,k,ans;
struct nyh{
	long long x,y,z;
}o[105];
double ans2;
long long read(){
	long long xx=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		ch=getchar();
	while(ch>='0'&&ch<='9'){
		xx=xx*10+ch-'0';
		ch=getchar();
	}
	return xx;
}
long long pus(long long xx,int flagg){
	if(xx>=10)
		pus(xx/10,0);
	putchar(xx%10+'0');
	if(flagg==1)
		putchar(' ');
	if(flagg==2)
		putchar('\n');
}
int ss(long long j,long long u,long long v){
	if(j>n){
		ans=max(ans,u*u+v*v);
		return 0;
	}
	if(j<=10||u*u+v*v<=(u+o[j].x)*(u+o[j].x)+(v+o[j].y)*(v+o[j].y))
		ss(j+1,u+o[j].x,v+o[j].y);
	if(j<=10||u*u+v*v>(u+o[j].x)*(u+o[j].x)+(v+o[j].y)*(v+o[j].y))
		ss(j+1,u,v);
}
bool cmp(nyh u,nyh v){
	return u.z<v.z;
}
int main(){
	n=read();
	for(i=1;i<=n;i++)
		scanf("%lld%lld",&o[i].x,&o[i].y);
	for(i=1;i<=1000;i++){
		srand(i*i*123+i*456);
		for(k=1;k<=n;k++)
			o[k].z=rand();
		sort(o+1,o+n+1,cmp);
		ss(1,0,0);
	}
	ans2=sqrt(ans);
	printf("%.13lf\n",ans2);
	return 0;
}

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

using namespace std;

int main()
{
    string str;
    cin>>str;
    int flag = 0;
    for(int i = 0; i < 4; i++)
    {
        if(count(str.begin(), str.end(), str[i]) != 2)
        {    
            cout<<"No";
            return 0;
        }
    }
    cout<<"Yes";
    return 0;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
sortsecond = lambda val: val[1]
x = [list(map(int, input().split())) for _ in range(M)]
x.sort(key=sortsecond)

i = 0
for j in range(M):
  times = x[-(j+1)][0]
  num = x[-(j+1)][1]
  while (times > 0):
    try:
      tmp = A[i]
    except IndexError:
      print(sum(A))
      exit()
    
    if (tmp < num):
      A[i] = num
    else:
      print(sum(A))
      exit()
    times -= 1
    i += 1

print(sum(A))

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

int main() {
  int s[3] = {};
  string str;
  cin >> str;
  
  int ans = 0;
  for( int i = 0; i < 3; ++i){
    s[i] = str[i]-'0';
    
    if( s[i] == 1 ){
      ++ans;
    }
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n,mi,ans;
  cin >> n;
  vector<int> p(n);
  for(int i=0;i<n;i++){
    cin >> p.at(i);
  }
  mi = p.at(0);
  for(int i=0;i<n;i++){
    if(p.at(i) <= mi){
      ans++;
    }
    mi = min(mi,p.at(i));
  }
  cout << ans << endl;
}

Measured memory_bytes: 4028
#include <iostream>
#include <iomanip>
#include <utility>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <cmath>
#include <cstring>
#include <map>
#include <climits>
#include <bitset>

#define ll long long
const ll INF = 100000000000;

struct Edge
{
    int to, rev;
    ll capacity;

    Edge(int to_, ll capacity_, int rev_)
            : to(to_), capacity(capacity_), rev(rev_){}
};

ll DFS(int current, int target, ll flow,
        std::vector<std::vector<Edge>>& connection,
        std::vector<bool>& seenTable)
{
    if (current == target)
        return flow;

    seenTable[current] = true;
    for (auto& e : connection[current])
    {
        if (!seenTable[e.to] && 0 < e.capacity)
        {
            auto d = DFS(e.to, target, std::min(flow, e.capacity), connection, seenTable);
            if (0 < d)
            {
                // d だけ e に流す
                e.capacity -= d;

                // d だけ 逆編から流れる
                connection[e.to][e.rev].capacity += d;

                return d;
            }
        }
    }

    return 0;
}

ll MaxFlow(int s, int t, std::vector<std::vector<Edge>>& connection)
{
    std::vector<bool> seenTable(connection.size());

    ll flow = 0;
    while (true)
    {
        for (auto i=0; i<seenTable.size(); ++i)
            seenTable[i] = false;

        ll f = DFS(s, t, INF, connection, seenTable);
        if (f == 0)
            return flow;
        else
            flow += f;
    }
}

int main()
{
    int N;
    std::cin >> N;
    std::vector<ll> A(N + 1);
    std::vector<std::vector<Edge>> graph(N + 3);

    ll maxSum = 0;
    for (auto i=1; i<=N; ++i)
    {
        std::cin >> A[i];
        if (0 < A[i])
            maxSum += A[i];
    }

    const int S = N + 1;
    const int T = N + 2;

    auto Connect = [&](int from, int to, ll capacity)
            {
                graph[from].push_back(Edge(to, capacity, graph[to].size()));
                graph[to].push_back(Edge(from, 0, graph[from].size() - 1));
            };

    for (auto i=1; i<=N; ++i)
    {
        if (A[i] < 0)
            Connect(S, i, -A[i]);
        else
            Connect(i, T, A[i]);

        for (auto j=i; j<=N; j += i)
            Connect(i, j, INF);
    }

    auto breakScore = MaxFlow(S, T, graph);
    std::cout << maxSum - breakScore << std::endl;
}


Measured memory_bytes: 3672
#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXN=100000;

int n;
int a[MAXN];


void run() {
	scanf("%d",&n); REP(i,n) scanf("%d",&a[i]);
	int nodd=0; REP(i,n) if(a[i]%2==1) ++nodd;
	printf("%s\n",nodd%2==0?"YES":"NO");
}

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


Measured memory_bytes: 640
#include "bits/stdc++.h"
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <map>
#include <vector>
#include <math.h>
#include <algorithm>
#include <queue>
#include <set>
#include <tuple>
using namespace std;

#define FOR(i,init,a) for(int i=init; i<a; i++)
#define rep(i,a) FOR(i,0,a)
#define rrep(i,a) for(int i=a; i>=0; i--)
#define rep1(i,a) for(int i=1; i<=a; i++)
#define cout1(a) cout << a << endl;
#define cout2(a,b) cout << a << " " << b << endl;
#define cout3(a,b,c) cout << a << " " << b << " " << c << endl;
#define cout4(a,b,c,d) cout << a << " " << b << " " << c << " " << d << endl;
#define mem(a,n) memset( a, n, sizeof(a))
#define all(a) a.begin(),a.end()
#define chmin(a,b) a=min(a,b);
#define chmax(a,b) a=max(a,b);

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LLINF = 1e18;
static const double pi = 3.141592653589793;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    string s;
    cin>>s;
    
    int cnt=1,mx=0;
    rep(i,3){
        if(s[i]==s[i+1]) cnt++;
        else cnt=1;
        chmax(mx,cnt);
    }
    
    cout1((mx>=3?"Yes":"No"))
}

Measured memory_bytes: 256
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author Sagor
 */

#include <fstream>
#include <fstream>
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>

#define gap                  ' '
#define EPS                  1e-9
#define mod                  1e9+7
#define P_INF                1e9+17
#define N_INF               -1e9+17
#define pi                   2*acos(0.0)
#define fi(s, n)             for(int i=s; i<n; i++)
#define fj(s, n)             for(int j=s; j<n; j++)
#define rfk(s, n)            for(int k=n-1; k>=s; k--)
#define unique(a)            a.resize(unique(a.begin(), a.end()) - a.begin())

typedef double ld;
typedef long long int ll;
typedef unsigned long long int ul;
using namespace std;

class CRally {
public:
    void solve(std::istream &in, std::ostream &out) {
        ll n, sum = 0, totalStamina = 0;
        in >> n;
        ll a[n];
        fi(0, n) {
            in >> a[i];
            sum += a[i];
        }
        ll median = (ll) round((double) sum / n);
        fi(0, n) {
            totalStamina += ((a[i] - median) * (a[i] - median));
        }
        out << totalStamina << endl;

    }
};


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


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <utility>
#include <functional>
typedef long long ll;
using namespace std;
int main(){
    int n,r;
    cin >> n >> r;

    if(n >= 10)cout << r << endl;
    else{
        cout << r + 100*(10 - n) << endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vs=vector<string>;
using msi=map<string,int>;
using mii=map<int,int>;
using psi=pair<string,int>;
using pii=pair<int,int>;
using vlai=valarray<int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define INF 1e9
#define EPS 1e-9
#define MOD (1e9+7)
void get(){}template<class H,class...T>void get(H&h,T&...t){cin>>h;get(t...);}
template<class T>void geti(T&a){for(auto&_:a)cin>>_;}
template<class T>void getii(T&a){for(auto&_:a)geti(_);}
void put(string d){}template<class H,class...T>void put(string d,H&h,T&...t){cout<<h;if(sizeof...(t))cout<<d;put(d,t...);}
template<class T>void puti(T&a,string d=" "){bool f=1;for(auto&_:a)cout<<(exchange(f,0)?"":d)<<_;cout<<endl;}
template<class T>void putii(T&a,string d=" "){for(auto&_:a)puti(_,d);}
#define dcl(...) ll __VA_ARGS__;get(__VA_ARGS__)
#define dclt(t,...) t __VA_ARGS__;get(__VA_ARGS__)

int main(){
	dcl(p);
	set<int> a;
	rep(i,p){dcl(t);a.insert(t);}
	int ans=0;
	dcl(q);
	rep(i,q){dcl(t);ans+=a.count(t);}
	cout<<ans<<endl;
	return 0;
}



Measured memory_bytes: 3156
n = int(input())
s = input()

check=1
if n%2==0:
    for i in range(int(n/2)):
        if s[i] == s[i+int(n/2)]:
            continue
        else:
            check=0
    if check==1:
        print("Yes")
    else:
        print("No")
else:
    print("No")

Measured memory_bytes: 3060
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <regex>

#define rep(i,n) for(int i = 0; i < n; i++)
#define prec(n) fixed << setprecision(n)
#define print_array(v) rep(__k, v.size()) { cout << v[__k]; if(__k != v.size()-1) cout << " "; else cout << endl; }
#define YesorNo(a) printf(a?"Yes\n":"No\n")
#define fi first
#define se second
#define endl "\n"
using namespace std;

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

//constexpr int inf = 2147483647;
//constexpr int64_t inf64 = 9223372036854775807;
//constexpr int mod = 1e9+7;

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

  int p, q, r;
  cin >> p >> q >> r;

  cout << min({p+q, q+r, r+p}) << endl;
  return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <string>
#include <sstream>
#include <iomanip>
#include <map>
#include <unordered_map>
#include <stack>
#include <cstdio>
#include <climits>
#include <tuple>
#include <ctime>
#include <cstring>
#include <numeric>
#define FOR(i,a,n) for (int i = a; i < n; i++)
#define IFOR(i,n,a) for (int i = n; i >= a; i--)
#define mp make_pair
#define full(a) a.begin(), a.end()
#define sz(x) ((int)(x).size())
#define pii pair<int, int>
#define trav(a,x) for (auto& a : x)
using ull = unsigned long long;
using ll = long long;
using ld = long double;
using namespace std;
const ll mod = 1e9 + 7;
const int N = 5005;

void solve()
{
    string s; cin >> s;
    string res(sz(s), 'x');
    cout << res;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    /*int tc;  cin >> tc;
    while (tc--)*/
        solve();
    return 0;
}







Measured memory_bytes: 3608
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
const ll mod=1000000007;
const int MAX_N = 1000;         // n の最大値
 
// nCk を取得
double nCk(int n, int k) {
double res=1.0;
for(int i=0; i<n; i++){
res*=0.5;}
for(int i=0; i<k; i++){
res*=(double)(n-i);
res/=(double)(k-i);
}
return res;}
 
int main() {
ll n;
cin>>n;
ll c=0;
ll a[n]={};
for(ll i=0; i<n; i++){
cin>>a[i];}
for(ll i=0; i<n; i++){
if(a[a[i]-1]==i+1){
c++;}}
cout<<c/2<<endl;}


Measured memory_bytes: 4400
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    a = LI()
    r = [0] * 60
    t = [0] * 60
    u = [0] * 60
    ii = [2**i for i in range(60)]
    for k in a[::-1]:
        for i in range(60):
            if k & ii[i] > 0:
                r[i] += u[i]
                t[i] += 1
            else:
                r[i] += t[i]
                u[i] += 1

    rr = 0
    for i in range(60):
        rr += r[i] * ii[i]
        rr %= mod

    return rr


print(main())




Measured memory_bytes: 120940
#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;
const int Maxn = 100010;
int n;
int a[Maxn];

int main() {
	
	scanf("%d",&n);
	for(register int i=1; i<=n; i++)
		scanf("%d",&a[i]);
	
	register ll ans = 0;
	for(register int i=1; i<n; i++) {
		register int tmp = a[i] >> 1ll;
		a[i] -= tmp << 1ll;
		ans += tmp;
		tmp = min(a[i],a[i+1]);
		a[i] -= tmp;
		a[i+1] -= tmp;
		ans += tmp;
	}
	
	ans += a[n] >> 1ll;
	printf("%lld\n",ans);
	
	return 0;
	
}

Measured memory_bytes: 640
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;
using static System.Math;
using System.Numerics;

namespace AtCoder
{
    class Program
    {
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }
        static long Mod = (long)1e9 + 7;
        static void Main(string[] args)
        {
            SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
            Solve();
            Out.Flush();
            Read();
        }
        static void Solve()
        {
            var N = Sarray()[0];
            var Ai = Sarray();

            var dct = new Dictionary<long, long>();
            for (var i = 0; i < N; ++i)
            {
                var k = i + 1 - Ai[i];
                if (!dct.ContainsKey(k)) dct[k] = 0;
                ++dct[k];
            }
            var ans = 0L;
            for (var i = 0; i < N; ++i)
            {
                var k = i + 1 + Ai[i];
                var d = i + 1 - Ai[i];
                --dct[d];
                if (dct.ContainsKey(k))
                    ans += Max(dct[k], 0);
            }
            WriteLine(ans);
        }
    }
}

Measured memory_bytes: 57636
import java.util.Scanner;

public class Main{


    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String str;
        int w = sc.nextInt();
        int n = sc.nextInt();
        int[]  tate = new int[w];
        for(int i=0;i<w;i++) {
        	tate[i]=i+1;
        }
        int[]   a   = new int[n];
        int[]   b   = new int[n];
        for(int i=0;i<n;i++){
        	str = sc.next();
        	String[] input = str.split(",");
            a[i]= Integer.parseInt(input[0]);
            b[i]= Integer.parseInt(input[1]);
            int t=tate[a[i]-1];
            tate[a[i]-1]=tate[b[i]-1];
            tate[b[i]-1]=t;
        }

        for(int i=0;i<w;i++){
            System.out.println(tate[i]);
        }
        sc.close();
    }
}


Measured memory_bytes: 26388
#include<bits/stdc++.h>
#include<limits>
#define ll long long
#define F first
#define S second
#define pb push_back
#define oo (1LL<<63-1)
#define endl '\n'
#define si size()
#define all(v) v.begin(),v.end()
#define FASTIO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define Matrix vector< vector < long long > >

using namespace std;

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

const long double Pi=acos(-1),e=2.718;
const int N=2e5+10,mod=1e9+7;
void Resize_Matrix(long long n , long long m , Matrix &M){
    M.clear();
    for(int j=0;j<n;j++) {
        M.push_back( vector< long long >() );
        M[j].resize(m);
        for(int i=0;i<m;i++) M[j][i]=0;
    }
}
Matrix Matrix_Multiplication(Matrix A , Matrix B){
    Matrix Ans; long long n , m;
    Resize_Matrix(n=A.size() , m=A[0].size() , Ans);
    for(long long j=0;j<n;j++){
        for(long long i=0;i<m;i++){
            Ans[j][i]=0;
            for(long long k=0;k<m;k++){
                Ans[j][i]+= A[j][k]*B[k][i];
                Ans[j][i]%=mod;
            }
        }
    }
    return Ans;
}
Matrix Matrix_Exponentiation(Matrix M , long long power){
    if(power==1) return M;
    Matrix ret=Matrix_Exponentiation(M , power/2);
    ret=Matrix_Multiplication(ret , ret);
    if(power%2) ret=Matrix_Multiplication(ret , M);
    return ret;
}

int main()
{
    FASTIO
    ll n , k;
    cin >> n >> k;
    Matrix a;
    Resize_Matrix(n,n,a);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin >> a[i][j];
        }
    }
    a = Matrix_Exponentiation(a,k);
    int sum=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            sum += a[i][j];
            sum %= mod;
        }
    }
    cout << sum << endl;
    return 0;
}
/**

*/


Measured memory_bytes: 1664
val ms = intArrayOf(2, 3, 4, 5, 6, 7, 8)
val num = intArrayOf(0,2,5,5,4,5,6,3,7,6)
val max_num = intArrayOf(0,0,0,0,0,0,0,0,0,0)

fun main(args: Array<String>) {
    val (n, m) = readLine()!!.split(" ").map(String::toInt)
    val a = readLine()!!.split(" ").map(String::toInt)
    for(i in 0 until m){
        max_num[num[a[i]]] = Math.max(max_num[num[a[i]]], a[i])
    } 
    val dp = Array<Int>(n+1, {-100000000})
    for(i in 0 until m){
        if(num[a[i]] > n) continue
        dp[num[a[i]]] = Math.max(dp[num[a[i]]], 1)
    }
    dp[0] = 0
    for(i in 2..n){
        for(j in 2..9){
            if(max_num[j] == 0) continue
            if(i-j >=0) dp[i] = Math.max(dp[i], dp[i-j]+1) 
        }
    }
    var cur = n
    while(cur > 0){
        var mx = -1
        var mm = 0
        for(i in 2..9){
            if(max_num[i] == 0) continue
            if(cur-i >= 0){
                if(mx < max_num[i] && dp[cur]==dp[cur-i]+1){
                    mx = max_num[i]
                    mm = i
                }
            }
        }
        print(mx)
        cur -= mm
    }
    println()
}


Measured memory_bytes: 40900
#include<iostream>
using namespace std;
int main()
{
	int x1,y1,x2,y2,x3,y3,x4,y4,a,b;
	cin>>x1>>y1>>x2>>y2;
	a=x2-x1;
	b=y2-y1;
	x3=x2-b;
	y3=y2+a;
	x4=x3-a;
	y4=y3-b;
	cout<<x3<<' '<<y3<<' '<<x4<<' '<<y4;
 } 

Measured memory_bytes: 256
n = int(input())
l = list(map(int,input().split()))
s = list(set(l))
if len(s)> 2:
    print("No")
    exit()
if len(s) == 1:
    if s[0] == n-1 or s[0] <= n//2:
        print("Yes")
    else:
        print("No")
    exit()
if abs(s[0]-s[1])>1:
    print("No")
    exit()
x,y = min(s),max(s)
a = l.count(x)
b = n-a
if a+b//2 >= y and a <= x:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 20812
#include <bits/stdc++.h>
using namespace std;
int main (){
  int N,m,A,n,k;
  cin>>N;
  m=2;
  for(int i=0;i<N;i++){
      n=0;
    cin>>A;
    for(int j=0;true;j++){
      if(A%m==0){
        n++;
        m*=2;
      }
      else{
        m=2;
        break;
      }
    }
     if(i==0){
        k=n;
      }
      else{
        if(k>n){
          k=n;
        }
      }
  }
  cout<<k<<endl;
}
  



Measured memory_bytes: 3572
#include<bits/stdc++.h>
#include<boost/variant.hpp>
using namespace std;
typedef long long ll;
typedef vector<boost::variant<bool, ll, int, string, double, char*, const char*>> any;
template<typename T> inline void pr(const vector<T> &xs){
	for(int i=0; i<xs.size()-1; i++) cout<<xs[i]<<" ";
	(xs.empty()?cout:(cout<<xs[xs.size()-1]))<<endl;
}
#ifdef DEBUG
#define debug(...) pr(any{__VA_ARGS__})
#define debugv(x) pr((x))
#else
#define debug(...)
#define debugv(x)
#endif

const ll P = 998244353;
ll fact[400000];

// Extended Euclid's greatest common divisor algorithm
// Find (x, y, g)
// where $a*x + b*y = g$ and g is the greatest common divisor of (a, b)
ll ext_gcd(ll a, ll b, ll &x, ll &y){
	if(b == 0){
		x = 1;
		y = 0;
		return a;
	}
	ll nx, ny;
	ll g = ext_gcd(b, a%b, nx, ny);
	x = ny;
	y = nx - a/b *ny;
	return g;
}

// Modular inverse of x given modulo p, y
// x*y = 1 mod p
// <=> x*y + z*p = 1
ll inv_mod(ll x, ll p){
	ll y,z;
	ext_gcd(x, p, y, z);
	return y>=0 ? y : p+(y%p);
}


// Modular factorial of n, also counting p's appearance e
// n! = a * p^e
// return: a % p
// n! = n * (n-1) * ... * (k*p+1) *
//      (k*p) * (k*p-1) * ... ((k-1)*p+1) *
//      ...
//      p * (p-1) * ... * 2 * 1   (k = floor(n/p))
//    = (n%p) * ... * 1 *
//      (k*p) * (p-1) * ... * 1 *
//      p * (p-1) * ... * 1       (mod p, preserving p's multiples)
//    = (n%p)! * p^k * k! * (p-1)^k
//    = (n%p)! * p^k * k! * (p-1)^(k%2)
//
// From the facts:
//   (p-1)! = p-1 (mod p) (c.f. Willson's theorem)
//   (p-2)**2 = 1 (mod p)
ll fact_mod(ll n, ll p, ll &e){
	if(n == 0){
		e = 0;
		return 1;
	}

	ll na = fact_mod(n/p, p, e);

	e += n/p;
	ll a = na * fact[n%p] % p;

	if((n/p)%2) a = a * (p-1)%p;
	return a;
}


// Modular combination (n, m) given module p
// (n, m) = n!/(n-m)!m!
//        = (a_n * p^(e_n)) / ((a_{n-m} * p^(e_{n-m}) * (a_m * p^e_m))
//        = a_n / (a_{n-m} * a_m) * p^(e_n - e_{n-m} - e_m)
ll comb_mod(ll n, ll m, ll p){
	ll e1,e2,e3;
	ll a1 = fact_mod(n, p, e1);
	ll a2 = fact_mod(m, p, e2);
	ll a3 = fact_mod(n-m, p, e3);

	if(e1 > e2+e3) return 0;
	else return a1*inv_mod(a2*a3%p, p)%p;
}

int main(){
	int N, A, B;
	ll K;
	cin >> N >> A >> B >> K;

	fact[0] = fact[1] = 1;
	for(int i=2; i<400000; i++) fact[i] = fact[i-1]*i%P;

	ll ans = 0;
	for(int i=0; i<=N; i++){
		if((K-(ll)i*A)%B) continue;
		ll j = (K-(ll)i*A)/B;
		if(j<0 || N<j) continue;

		ans += comb_mod(N, i, P) * comb_mod(N, j, P) % P;
		ans %= P;
	}

	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3328
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <random>
#include <chrono>
#include <utility>
#include <numeric>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <sstream>
#include <assert.h>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <unordered_map>
using namespace std;

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(bool x) {cerr << (x ? "true" : "false");}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}

template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";}
template <typename T, typename... V>void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef HOME
#warning CHECK int:ll::INT_MAX:LLONG_MAX
#define maxn 20
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define maxn 2000006
#define gcd __gcd
#define debug(x...)
#endif

#define ff first
#define endl '\n'
#define ss second
#define inf 0x3f3f3f3f
#define MOD 1000000007
#define PI 3.14159265358979323846264338327950L
#define f(i,x,n) for(int i=x;i<=n;i++)
#define fr(i,x,n) for(int i=x;i>=n;i--)
struct _ { ios_base::Init i; _() { ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL); } } _;

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


int main() {

	long long  n, m, k; cin >> n >> m >> k;
	vector<long long > va(n + 1, 0), vb(m + 1, 0), pa(n + 1, 0), pb(m + 1, 0);

	for (long long   i = 1; i <= n; i++) cin >> va[i], pa[i] = pa[i - 1] + va[i];
	for (long long   i = 1; i <= m; i++) cin >> vb[i], pb[i] = pb[i - 1] + vb[i];

	long long  ans = 0;
	for (long long  i = 0; i <= n; i++) {
		if (pa[i] > k) break;
		long long  j = prev(upper_bound(pb.begin(), pb.end(), k - pa[i])) - pb.begin();
		ans = max(ans, i + j);
	}

	cout << ans;

	return 0;
}

Measured memory_bytes: 9484
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,n) for(int i=(int)(j);i<(int)(n);i++)
#define REP(i,j,n) for(int i=(int)(j);i<=(int)(n);i++)
#define MOD 1000000007
#define int long long
#define ALL(a) (a).begin(),(a).end()
#define vi vector<int>
#define vii vector<vi>
#define pii pair<int,int>
#define priq priority_queue<int>
#define disup(A,key) distance(A.begin(),upper_bound(ALL(A),(int)(key)))
#define dislow(A,key) distance(A.begin(),lower_bound(ALL(A),(int)(key)))
#define tii tuple<int,int,int>
#define Priq priority_queue<int,vi,greater<int>>
#define pb push_back
#define mp make_pair
#define INF (1ll<<60)
signed main(){
  int N,M,L; cin>>N>>M>>L;
  vector<vector<pii>> A(N),F(N,vector<pii>(N,mp(INF,L)));
  rep(i,0,M){
    int X,Y,Z; cin>>X>>Y>>Z;
    if(L>=Z){
      A[X-1].pb(mp(Y-1,Z));
      A[Y-1].pb(mp(X-1,Z));
    }
  }
  rep(i,0,N){
    priority_queue<pair<pii,int>,vector<pair<pii,int>>,greater<pair<pii,int>>> Q;
    Q.push(mp(mp(0,0),i));
    F[i][i]=mp(0,0);
    while(Q.size()>0){
      int X=Q.top().second,Y=Q.top().first.first,Z=Q.top().first.second;
      Q.pop();
      if(mp(Y,Z)>F[i][X]) continue;
      rep(j,0,A[X].size()){
        int P=A[X][j].first,R=A[X][j].second;
        if(P!=X){
        int B=Z+R,C=Y;
        if(B>L){
          B=R;
          C++;
        }
        if(F[i][P]>mp(C,B)){
          F[i][P]=mp(C,B);
          Q.push(mp(mp(C,B),P));
        }
        }
      }
    }
  }
  int Q; cin>>Q;
  rep(i,0,Q){
    int X,Y; cin>>X>>Y;
    int ans=F[X-1][Y-1].first;
    if(ans==INF) ans=-1;
    cout<<ans<<endl;
  }
  }




Measured memory_bytes: 5684
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector< ll > vi;
typedef vector< vi > vvi;
typedef pair< ll,ll > ii;
#define fr(i,a,b) for(ll i=a;i<=b;i++)
#define rfr(i,a,b) for(ll i=a;i>=b;i--)
#define tr(x,i) for(vi::iterator i = x.begin() ; i != x.end() ; i++)
#define sz(a) ll((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define T ll t;cin>>t;while(t--)
ll powmod(ll a,ll b){ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
signed main() 
{
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL);
	cout.tie(NULL);
	ll n,m;
	cin>>n>>m;
	ll ans = n*(n-1)/2;
	ans += m*(m-1)/2;
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 764
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define endl "\n"
#define se second
#define ls( s) (s&(-s))
#define ll long long
#define inf 0x3f3f3f3f
#define fast    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int N = 2e5;
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
const ll mod =    1e9+7;
ll arr[N];
int main()
{  fast
ll n,k;
cin>>n>>k;
ll ans=0;
for(ll i=1;i<=n;i++)
{
	arr[i]=i+arr[i-1];
}

for(ll i=k-1;i<=n;i++)
{
	ll x=arr[i];
	ll y=arr[n]-arr[n-i-1]+1;
	ans=(ans+(y-x))%mod;
	//cout<<y<<" "<<x<<endl;
}
cout<<ans;
}


Measured memory_bytes: 5100
#include <stdio.h> 
 #include <ctype.h>
  
 
 int main(){ 
     char ch; 
     while(1){ 
         scanf("%c", &ch); 
         if(ch=='\n'){ 
             printf("\n"); 
             break; 
         }else if(islower(ch)){ 
             printf("%c", toupper(ch)); 
         }else if(isupper(ch)){ 
             printf("%c", tolower(ch)); 
         }else{ 
             printf("%c", ch); 
         } 
     } 
 
      return 0; 
 } 



Measured memory_bytes: 2048
/*------------------------------------
........Bismillahir Rahmanir Rahim....
..........created by Abdul Aziz.......
------------------------------------*/
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cmath>
#include <vector>
#include <set>
#include <list>
#include <stack>
#include <map>
#include <cstring>
#include <unordered_map>
#include <queue>
#include <functional>
#define   mod  998244353
#define   int  long long 
#define   ld   long double
#define   pb   push_back
#define   vi   vector<int> 
#define   co(x)  cout << x << '\n' 
#define   dbg(x)  cerr << #x << " = " << x << '\n' 
#define   bitcount(x)  (int)__builtin_popcount(x) 
#define   sz(x)  (int)x.size()
#define   all(a) a.begin(),a.end() 
#define   ff   first
#define   ss   second
#define   pii  pair<int,int> 
#define   lcm(a,b) (a*b)/__gcd(a,b) 
using namespace std;

inline void solve(){
    int  n, ans = 0 ; 
    cin >> n ; 
    vi  a(n+1) ; 
    for (int i=1;i<=n;i++) cin >> a[i] ; 
    int sum = 0, xr = 0, cnt = 0 ; 
	for (int i=1;i<=n;i++){
		sum += a[i] ; 
		xr = xr^a[i] ; 
		if (xr == sum) cnt++ ; 
		else {
			int cur = cnt ; 
			while (sum != xr){
				sum -= a[i-cnt];
				xr ^= a[i-cnt] ;
				cnt--;
			}
			ans += cur * (cur+1) / 2 ; 
			ans -= cnt * (cnt+1) / 2 ; 
			cnt++; 
		}
	}
	ans += cnt * (cnt+1) / 2 ; 
	co (ans) ; 
}
signed main()
{
    int n=1; // cin>>n;
    while (n--) solve();
    return 0;
}


Measured memory_bytes: 4840
main :: IO ()
main = do
    s <- getLine :: IO String
    let d01 = read $ take 2 s
        d23 = read $ drop 2 s
    putStrLn $ case (1 <= d01 && d01 <= 12, 1 <= d23 && d23 <= 12) of
        (True , True ) -> "AMBIGUOUS"
        (True , False) -> "MMYY"
        (False, True ) -> "YYMM"
        _              -> "NA"


Measured memory_bytes: 508
#include <bits/stdc++.h>
#define ll long long
#define inf 1e9
using namespace std;

int main() {
    int n,k,v;
    cin>>n>>k;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    vector<int> dp(n,inf);
    dp[0] = 0;
    dp[1] = abs(a[1]-a[0]);
    for(int i=2;i<n;i++){
        for(int j=1;j<=k && i-j>=0;j++){
            v = dp[i-j] + abs(a[i]-a[i-j]);
            dp[i] = min(dp[i],v);
        }
    }
    cout<<dp[n-1];
	return 0;
}

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

int main(){
	int N, i, j;
	double L;
	scanf("%d%lf", &N, &L);
	vector<double> T(N);
	for(i = 0; i < N; i++){
		scanf("%lf", &T[i]);
	}
	double sumx = 0, sumy = 0;
	double ZPi_L = 2 * M_PI / L;
	for(i = 0; i < N; i++){
		for(j = i + 1; j < N; j++){
			double t1 = (T[i] + T[j]) / 2;
			double t2 = t1 + L / 2;
			if(t2 >= L){
				t2 -= L;
			}
			int k1 = j - i - 1;
			int k2 = N - k1 - 2;
			sumx += k1 * cos(t2 * ZPi_L) + k2 * cos(t1 * ZPi_L);
			sumy += k1 * sin(t2 * ZPi_L) + k2 * sin(t1 * ZPi_L);
		}
	}
	double n = ((double)N * (N - 1) * (N - 2)) / 6;
	printf("%.20lf %.20lf\n", sumx / n, sumy / n);
	return 0;
}

Measured memory_bytes: 384
# import sys
# input = sys.stdin.readline
import collections
import itertools

def main():
    h, w = input_list()
    maze = [list(input()) for _ in range(h)]
    ans = []
    blacks = [False] * w
    for m in maze:
        for i, v in enumerate(m):
            if v == "#":
                blacks[i] = True
    for m in maze:
        f = True
        new_row = []
        for i, b in enumerate(blacks):
            if b:
                new_row.append(m[i])
        for i, v in enumerate(new_row):
            if v == "#":
                f = False
                break
        if f:
            continue
        ans.append(new_row)
    for a in ans:
        print("".join(a))


def input_list():
    return list(map(int, input().split()))


def input_list_str():
    return list(map(str, input().split()))


if __name__ == "__main__":
    main()


Measured memory_bytes: 68572
a,b,n = map(int,input().split())
ma = 0

if(n<b):
    ma = (a*n)//b - (a* (n//b))
else:
    ma = (a*(b-1))//b - (a*((b-1)//b))
    """
    for x in range(b,n+1):
        
        num = (a*x)//b - (a*(x//b))
        if(ma > num):
            break
        ma = num
    """

print(ma)

Measured memory_bytes: 9140
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define uint ungigned
#define db double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pli pair<ll,int>
#define vi vector<int>
#define vpi vector<pii >
#define IT iterator
 
#define PB push_back
#define MK make_pair
#define LB lower_bound
#define UB upper_bound
#define y1 wzpakking 
#define fi first
#define se second
#define BG begin
#define ED end
 
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define UPD(x,y) (((x)+=(y))>=mo?(x)-=mo:233)
#define CLR(a,v) memset(a,v,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(a))
#define sqr(x) (1ll*x*x)
 
#define LS3 k*2,l,mid
#define RS3 k*2+1,mid+1,r
#define LS5 k*2,l,mid,x,y
#define RS5 k*2+1,mid+1,r,x,y
#define GET pushdown(k);int mid=(l+r)/2
#define INF (1<<29)
using namespace std;
const int N=1505;
char s[N];
int n,cnt[N];
ll ans;
int a[N][N],sum[N][N];
int tl[N][N],tr[N][N];
void recalc(int i){
	For(j,1,n) sum[i][j]=sum[i][j-1]+a[i][j];
}
int S(int i,int l,int r){
	return sum[i][r]-sum[i][l-1];
}
int main(){
	scanf("%d",&n);
	For(i,1,n){
		scanf("%s",s+1);
		For(j,1,n) a[i][j]=(s[j]=='#'?0:s[j]-48);
		recalc(i);
	}
	For(i,1,n) For(j,1,n+1)
		tl[i][j]=n+1,tr[i][j]=0;
	For(y,1,n) Rep(j,n,1) if(a[y][j]){
		tl[y][j]=j; tr[y][j]=max(j,tr[y][j+1]);
		ans+=a[y][j]*S(y,tl[y][j]+1,tr[y][j]);
	}
	Rep(x,n,1) For(y,x+1,n){
		Rep(j,n,1)
			if (a[x][j]){
				tl[y][j]=min(tl[y][j],tl[y][j+1]);
				tr[y][j]=max(tr[y][j],tr[y][j+1]);
			}
			else tl[y][j]=n+1,tr[y][j]=0;
		For(j,1,n) cnt[j]=0;
		For(j,1,n) if (tl[y][j]<=tr[y][j]){
			ans+=a[x][j]*(sum[y][tr[y][j]]-sum[y][tl[y][j]-1]);
			++cnt[tl[y][j]]; --cnt[tr[y][j]+1];
		}
		bool flag=0;
		For(j,1,n){
			cnt[j]+=cnt[j-1];
			if (!cnt[j]&&a[y][j])
				a[y][j]=0,flag=1;
		}
		if (flag) recalc(y);
	}
	printf("%lld",ans);
}

Measured memory_bytes: 20736
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lvector vector<ll> 
#define P pair<ll,ll>
#define rep(i,n) for(ll (i)=0; i<(n); ++(i))
#define print(a) cout << (a) << endl

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll n,t,a,ans=0,h=0;cin>>n;cin>>t>>a;
  double diff=1000000000.0,diff_=0.0;
  rep(i,n) {
    cin>>h;
    diff_=abs(a-(t-h*0.006));
    if(diff>diff_) {diff=diff_;ans=i+1;}
  }
  print(ans);
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define ll long long 
#define rep(i,a,b) for(signed i=a;i<(b);++i)
#define erep(i,a,b) for(signed i=a;i<=(b);++i)
#define per(i,a,b) for(signed i=(a);i>(b);--i)
#define eper(i,a,b) for(signed i=(a);i>=b;--i)
#define fore(i, x, a) for(auto &&x:a) 
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define pb emplace_back
#define mp make_pair
#define ALL(x) begin(x),end(x)
#define F first
#define S second
#define debug(x)  cout << #x << ": " << (x) << '\n';
const long long INF=1001001001001001001;
const int MOD=(int)1e9 + 7;
const double EPS=1e-9;
using namespace std;
using Pii = pair<int,int>;
using vii = vector<int>;
template<class T>using  PS_queue = priority_queue<T, vector<T>, greater<T> >;
template<class T>using vv = vector<T>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
template<typename A, size_t N, typename T> void Fill(A (&array)[N], const T &val){fill( (T*)array, (T*)(array+N), val );}
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> ostream& operator<<(ostream &os,const vector<vector<T>> &v) {
    ITR(u,begin(v),end(v))ITR(w,begin(*u),end(*u))os<<*w<<(w==end(*u)-1?"\n":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T>T gcd(T a, T b){ return b ? gcd(b, a % b) : a; }
template<class T>T lcm(T a, T b){ return a / gcd(a, b) * b; }
struct edge { int from, to, cost; };
int dy[]={0, 1, -1, 0}; int dx[]={1, 0, 0, -1};
// cout << fixed;
// cout << setprecision(10) << val;

int partition(vector<pair<char, int>> &a, int p, int r) {
	int i = p-1, pivot = r;
	for (int j = p; j < r; j++) {
		if (a[j].S <= a[pivot].S) {
			swap(a[++i], a[j]);
		}
	}
	swap(a[pivot], a[++i]);
	return i;
}

void quickSort(vector<pair<char, int>> &a, int p, int r) {
	if (p < r) {
		int q = partition(a, p, r);
		quickSort(a, p, q-1);
		quickSort(a, q, r);
	}
}

int n;
vv<pair<char, int>> cards, stable_cards;

signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
	cin >> n;
	rep(i, 0, n) {
		char c;
		int k;
		cin >> c >> k;
		cards.push_back(make_pair(c, k));
		stable_cards.push_back(make_pair(c, k));
	}

	quickSort(cards, 0, n-1);
	stable_sort(stable_cards.begin(), stable_cards.end(), 
			[](const pair<char, int> &a, const pair<char, int> &b){ return a.S < b.S; });

	bool isStable = true;
	for (int i = 0; i < n; i++) {
		if (stable_cards[i] != cards[i]) {
			isStable = false;
			break;
		}
	}
	cout << (isStable ? "Stable" : "Not stable") << endl;
	for (auto x : cards) {
		cout << x.F << " " << x.S << endl;
	}
  return 0;
}




Measured memory_bytes: 7612
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    int a,b,c,n;
    while(cin>>a>>b>>c,a||b||c){
        cin>>n;
        int f[300];
        fill(f,f+300,2);
        int m=a+b+c;
        int x[1000],y[1000],z[1000];
        bool r[1000];
        for(int i=0;i<n;i++){
            cin>>x[i]>>y[i]>>z[i]>>r[i];
            x[i]--;y[i]--;z[i]--;
        }


        int cnt=0;
        while(cnt<100000){

            for(int i=0;i<n;i++){
                int a=x[i],b=y[i],c=z[i];
                bool Flag=r[i];
                if(Flag){

                    f[a]=f[b]=f[c]=1;
                }
                else{
                    if(f[b]==1&&f[c]==1){

                        f[a]=0;
                    }
                    if(f[a]==1&&f[c]==1){

                        f[b]=0;
                    }
                    if(f[a]==1&&f[b]==1){

                        f[c]=0;
                    }
                }
            }
            cnt++;
        }
        for(int i=0;i<m;i++)cout<<f[i]<<endl;
    }
}

Measured memory_bytes: 1172
#include<bits/stdc++.h>
using namespace std;
//#define int long long
typedef long long ll;
#define sqr(x) ((x)*(x))
#define pb push_back
const int N=1000002,M=998244353;
int pw(int x,int y){int z=1;for(;y;y>>=1,x=1ll*x*x%M)if(y&1)z=1ll*z*x%M;return z;}
void inc(int &x,int y){x+=y;if(x>=M)x-=M;}void dec(int &x,int y){x-=y;if(x<0)x+=M;}
void Max(int &x,int y){if(y>x)x=y;}void Min(int &x,int y){if(y<x)x=y;}
//struct node{int to,ne;}e[];
//void add(int x,int y){e[++tot]=(node){y,h[x]},h[x]=tot;}
int x,s,i,ss,n;
signed main(){
	scanf("%d",&n);
	for (i=1;i<=n;i++) scanf("%d",&x),s+=x,ss+=x*x;
	printf("%d",(s*s-ss)/2);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[300005];
ll pre[300005],suf[300005];
int main()
{
     int n,i,j;
     scanf("%d",&n);
     for(i=1;i<=3*n;i++)
     scanf("%d",&a[i]);
     j = 3*n;
     multiset<int> fir,sec;
     ll x,y;
     for(i=1;i<=n;i++)
     {
         fir.insert(a[i]);
         sec.insert(-a[j]);
         pre[i] = pre[i-1] + a[i];
         suf[j] = suf[j+1] + a[j];
       //  printf("%lld %lld %d %d\n",pre[i],suf[j],a[i],a[j]);
         j--;
         
     }
     for(;i<=2*n;i++)
     {
        fir.insert(a[i]);
        sec.insert(-a[j]);
        pre[i] = pre[i-1] + a[i] - *fir.begin();
        suf[j] = suf[j+1] + a[j] + *sec.begin();
        fir.erase(fir.begin());
        sec.erase(sec.begin());
        j--;
        
     }
     for(;i<=3*n;i++)
     {
         pre[i] = pre[i-1];
         suf[j] = suf[j+1];
         j--;
     }
   
     ll ans = pre[n] - suf[n+1];
     for(i=n+1;i<=2*n;i++)
     ans = max(ans, pre[i] - suf[i+1]);
     cout<<ans;
}

Measured memory_bytes: 15488
#include <stdio.h>

int gcd(int m, int n)
{
	int r;

	while (n > 0) {
		r = m % n;
		m = n;
		n = r;
	}
	return m;
}

int main()
{
	int a, b;

	while (scanf("%d %d", &a, &b) != EOF) {
		int gcd_val = gcd(a, b);
		printf("%d %d\n", gcd_val, a / gcd_val * b);
	}
	return 0;
}

Measured memory_bytes: 0
// بِسمِ اللہِ  الرَّحم?نِ  الرَّ حِیم
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define MOD 1000000007
#define ll long long
#define pb push_back
#define all(v) v.begin(),v.end()
#define INF 1e18
#define N 100100
#define PI 3.141592653589793238
typedef pair<ll,ll> pll;
ll power(ll a,ll b)
{
    if(b==1)return a;
    if(b==0)return 1;
    ll temp=power(a,b/2);
    ll ans=temp*temp;
    if(b&1)
        ans*=a;
    return ans;
}
ll power(ll a,ll b,ll p)
{
    a=a%p;
    if(b==1)return a;
    if(b==0)return 1;

    ll temp=power(a,b/2,p);
    ll ans=(temp*temp)%p;
    if(b&1)
        ans=(a*ans)%p;
    return ans%p;
}
ll inv(ll a,ll m)
{
    return power(a,m-2,m);
}
//code begins
void solve(){
    ll n,m,k;cin>>n>>m>>k;
    ll a[n+1]={0};
    for(ll i=1;i<=n;i++)cin>>a[i];
    ll b[m+1]={0};
    for(ll i=1;i<=m;i++)cin>>b[i];
    for(ll i=2;i<=n;i++)a[i]+=a[i-1];
    for(ll i=2;i<=m;i++)b[i]+=b[i-1];
    ll ans=0,i=0,j=m;
    while(i<=n)
    {
        if(a[i]>k)break;
        while(j>=0 and b[j]+a[i]>k)j--;
        ans=max(ans,i+j);
        i++;
    }
    cout<<ans<<endl;
}
signed main()
{
//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);

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

//    ll t;cin>>t;while(t--)
    solve();
    return 0;
}


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

int main(int argc, char const *argv[])
{
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i)	cin >> a.at(i);
	sort(a.begin(), a.end());
	cout << a.at(n - 1) - a.at(0) << endl;
	return 0;
}


Measured memory_bytes: 256