akhauriyash/Code-Regression huggingface dataset:
// Date: 2020-05-02

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

typedef long long LL;
typedef long double LD;
typedef vector<int> VI;
typedef pair<LL, LL> pll;
typedef pair<int, int> pii;
#define IO freopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout)
#define FIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define rep(i, a, b) for(int i = int(a); i <= int(b); ++i)
#define per(i, b, a) for(int i = int(b); i >= int(a); --i)
#define D(x) cout << #x << " = " << x << endl;
#define mem(x, y) memset(x, y, sizeof(x))
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)x.size())
#define mk make_pair
#define pb push_back
#define fi first
#define se second
const LL INF = 1e18;
const LL mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 10;
template <typename T> void chkmax(T &x, T y) { x = max(x, y); }
template <typename T> void chkmin(T &x, T y) { x = min(x, y); }
LL qpow(LL x, LL y, LL MOD) {LL a=1; while(y){ if(y&1) a=a*x%MOD; x=x*x%MOD; y>>=1; } return a;}

int a[N], b[N], n, m;
VI g[N];

#define mid ((l + r) >> 1)
#define lc (rt << 1)
#define rc (rt << 1 | 1)
#define lson lc, l, mid
#define rson rc, mid+1, r

int mx[N<<2], ans[N];

void update(int rt, int l, int r, int x, int v) {
    if(l == r) {
        mx[rt] = v;
        return;
    }
    if(x <= mid) update(lson, x, v);
    else update(rson, x, v);
    mx[rt] = max(mx[lc], mx[rc]);
}

int ask(int rt, int l, int r, int ql, int qr) {
    if(ql <= l && r <= qr) return mx[rt];
    int ans = 0;
    if(ql <= mid) chkmax(ans, ask(lson, ql, qr));
    if(qr > mid) chkmax(ans, ask(rson, ql, qr));
    return ans;
}

void dfs(int u, int fa) {
    for(auto v : g[u]) if(v != fa) {
        int val = ask(1, 0, m, 0, a[v]-1) + 1;
        ans[v] = max(ans[u], val);
        int pre = ask(1, 0, m, a[v], a[v]);
        if(val > pre) update(1, 0, m, a[v], val);
        dfs(v, u);
        update(1, 0, m, a[v], pre);
    }
}

int main() {
    FIO;
    cin >> n;
    rep(i, 1, n) cin >> a[i], b[i] = a[i];
    sort(b+1, b+1+n);
    m = unique(b+1, b+1+n)-b-1;
    rep(i, 1, n-1) {
        int u, v;
        cin >> u >> v;
        g[u].pb(v), g[v].pb(u);
    }
    rep(i, 1, n) a[i] = lower_bound(b+1, b+1+m, a[i])-b;
    ans[1] = 1;
    update(1, 0, m, a[1], 1);
    dfs(1, 0);
    rep(i, 1, n) cout << ans[i] << '\n';

    return 0;
}

Measured memory_bytes: 33928
N = int(input())
SPlist = []
for i in range(N):
    buff  = input().split()
    SPlist.append([i+1,str(buff[0]),int(buff[1])])
SPlist = sorted(SPlist,key = lambda x:x[2],reverse=True)
SPlist = sorted(SPlist,key=lambda x:x[1])
[print(i[0]) for i in SPlist]

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

using namespace std;

using ll = long long;
using ld = long double;

using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vs = vector<string>;

typedef pair<ll, ll> P;

#define bit(n) (1LL << (n))

//#define int long long

#define all(v) v.begin(), v.end()
#define sortAl(v) sort(all(v))
#define sortAlr(v)          \
  sort(v.begin(), v.end()); \
  reverse(v.begin(), v.end())

#define rep(i, n) for (ll i = 0; i < n; i++)
#define REP(i, n) for (ll i = 1; i < n; i++)

#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define FORm(i, m) for (auto i = m.begin(); i != m.end(); i++)

template <class T>
inline void chmax(T &a, T b) {
  a = std::max(a, b);
}
template <class T>
inline void chmin(T &a, T b) {
  a = std::min(a, b);
}

#define mod (ll)(1e9 + 7)
#define INF LLONG_MAX

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);

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

  if (a != b && b != c && c != a) {
    cout << "No" << endl;
  } else if (a == b && b == c) {
    cout << "No" << endl;
  } else {
    cout << "Yes" << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define P pair<int,int>
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1000000000
#define MOD 1000000007
#define all(v) v.begin(),v.end()
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int kaijo[222222];
struct edge{int to,cost;};
int gcd(int a,int b){
	if(b==0)return a;
	return gcd(b,a%b);
}
int lcm(int a,int b){
	return a/gcd(a,b)*b;
}
bool prime(int a){
	if(a==1)return false;
	for(int i=2;i*i<=a;i++){
		if(a%i==0)return false;
	}
	return true;
}
bool kosa(double ax,double ay,double bx,double by,double cx,double cy,double dx,double dy){//線分の交差判定
	double ta=(cx-dx)*(ay-cy)+(cy-dy)*(cx-ax);
	double tb=(cx-dx)*(by-cy)+(cy-dy)*(cx-bx);
	double tc=(ax-bx)*(cy-ay)+(ay-by)*(ax-cx);
	double td=(ax-bx)*(dy-ay)+(ay-by)*(ax-dx);
	return tc*td<0&&ta*tb<0;
}
void init_fact(int n){
	kaijo[0]=1;
	for(int i=1;i<=n;i++){
		kaijo[i]=kaijo[i-1]*i;
		kaijo[i]%=MOD;
	}
}
int modpow(int a,int b){
	if(b==0)return 1;
	if(b%2)return modpow(a,b-1)*a%MOD;
	int memo=modpow(a,b/2);
	return memo*memo%MOD;
}
int comb(int a,int b){
	return kaijo[a]*modpow(kaijo[a-b],MOD-2)%MOD*modpow(kaijo[b],MOD-2)%MOD;
}
int g(int x){
	x=modpow(x,MOD-2);
	return x;
}
int mi=1000000,memo=1000000;
signed main(){
	int n,l,ans=0;
	cin>>n>>l;
	for(int i=l;i<l+n;i++){
		if(mi>abs(i)){
			mi=abs(i);
			memo=i;
		}
	}
	for(int i=l;i<l+n;i++){
		ans+=i;
	}
	ans-=memo;
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main(){
	int n;
	while(true){
	cin>>n;
	if(n==0)
		break;
	int x,y,h,w;
	int ans=0;
	for(int u=0;u<n;u++){
		cin>>x>>y>>h>>w;
		int count=0;
		if(x+y+h<=160&&w<=25)
			count=1600;
		if(x+y+h<=140&&w<=20)
			count=1400;
		if(x+y+h<=120&&w<=15)
			count=1200;
		if(x+y+h<=100&&w<=10)
			count=1000;
		if(x+y+h<=80&&w<=5)
			count=800;
		if(x+y+h<=60&&w<=2)
			count=600;
		ans+=count;
	}
	cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 1156
fun main(args: Array<String>) {
    // Your code here!
    var s = readLine()!!.toList()
    var msg = "Good"
    
    for(i in 1..s.size-1){
        if(s[i-1] == s[i]){
            msg = "Bad"
            break
        }
    }

    println(msg)
}

Measured memory_bytes: 31952
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <string>
#include <utility>
#include <algorithm>
#include <functional>
#include <deque>
#define INT_INF 1000000000
#define DOUBLE_INF 1e18
#define MOD 1000000007
#define mod(x) ((x % MOD) + MOD) % MOD

using namespace std;

typedef long long ll;
typedef pair<int,int> P;

int main() {
  string s;
  cin >> s;
  int len = (int)s.size();

  char color = s[0];
  int ans = 0;
  for (int i = 1; i < len; i++) {
    if (color != s[i]) {
      ans++;
      color = s[i];
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 512
// ░░░░░░░░( •̪●)░░░░░░░░░░░░░░░░░░░░░░░░
// ░░░░░░███████ ]▄▄▄▄▄▄▄▄▃░░░▃░░░░ ▃░
// ▂▄▅█████████▅▄▃▂░░░░░░░░░░░░░░░░░
// [███████████████████].░░░░░░░░░░░░░░
// ◥⊙▲⊙▲⊙▲⊙▲⊙▲⊙▲⊙◤...░░░░░░░░░░░░

//PointBlank's code (⌐■_■)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
#define repp(I, A, B) for(int I = A; I <= B; I++)
#define rep(I, A, B) for(int I = A; I < B; I++)
#define rrep(I, B, A) for(int I = B; I >= A; I--)
#define pb emplace_back
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define LB lower_bound
#define UB upper_bound
#define MP make_pair
#define mem(A, B) memset(A, B, sizeof(A));
#define mem0(A) memset(A, 0, sizeof(A));
#define quickio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define in_edges(M) repp(I, 1, M){ll A, B; cin >> A >> B; v[A].pb(B), v[B].pb(A);}
#define in_edges2(M) repp(I, 1, M){ll A, B; cin >> A >> B; v[A].pb(B);}
#define endl "\n"
#define debug(this) cerr<<"> "<<#this<<" : "<<this<<"\n"
#define bitsf(n) __builtin_popcount(n)
ll power(ll x, ll y); 

const ll MOD = 1000000007;
 
int main() //PointBlank's code ¯\_(ツ)_/¯
{
    int n;
    string s;
    cin >> n >> s;

    int mx = 0;
    rep(i, 0, n - 1){
        set<char> a, b;
        repp(j, 0, i) a.emplace(s[j]);
        rep(j, i + 1, n) b.emplace(s[j]);
        int c = 0;
        for(auto ch : a) if(b.count(ch)) c++;
        mx = max(mx, c); 
    }
    cout << mx;
}
 
ll power(ll x, ll y)
{ 
    ll res = 1; x %= MOD;
    while(y > 0){if(y & 1) res = (res*x) % MOD; y = y>>1, x = (x*x) % MOD;} 
    return res; 
}


Measured memory_bytes: 256
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------
class Modinv:
    def __init__(self, n, mod):
        self.mod = mod
        self.fact = [1]*n
        self.finv = [1]*n
        self.inv  = [1]*n
        for i in range(2,n):
            self.fact[i] = (self.fact[i-1]*i) % self.mod
            self.inv[i]  = self.mod - self.inv[self.mod%i] * (self.mod//i)%self.mod
            self.finv[i] = self.finv[i-1] * self.inv[i] % self.mod
 
    def nCr(self, n, r):
        if n<r:
            return 0
        else:
            return self.fact[n] * (self.finv[r] * self.finv[n-r] % self.mod) % self.mod
    
    def nPr(self, n, r):
        if n<r:
            return 0
        else:
            return self.fact[n] * self.finv[n-r] % self.mod

mod = 10**9+7

# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N,K = map(int,input().split())
AB = [tuple(map(int,input().split())) for _ in range(N-1)]

A = [[] for _ in range(N)]
for a,b in AB:
    A[a-1].append(b-1)
    A[b-1].append(a-1)

Modinv = Modinv(K+10, mod)

# 頂点はK色どれでも塗ることが可能
ans = K

from collections import deque
dq = deque([(0,0)]) # 頂点0, 距離0
visited = [False]*N 

while dq:
    v,d = dq.pop()
    visited[v] = True
    cnt = 0 # 子がいくつあるか
    for e in A[v]:
        if visited[e]:
            continue
        cnt += 1
        dq.append((e, d+1))
    # 子がなければ何もしない
    if cnt==0:
        continue
    # 根の場合は, 根の1色以外を子に割り当て可能
    if d==0:
        n = Modinv.nPr(K-1,cnt)
    # それ以外の場合は, 親と自身の2色以外を子に割り当て可能
    else:
        n = Modinv.nPr(K-2,cnt)
    
    ans *= n
    ans %= mod

print(ans)

Measured memory_bytes: 55636
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=1000100;
struct edge{
    int from,to;
    double cost;
}es[maxn];
struct point{
    int x,y;
};
int pre[maxn],rank1[maxn];
int n,m;
bool comp(const edge& e1,const edge& e2)
    {
        return e1.cost>e2.cost;
    }
void init(int n)
    {
        for (int i=1;i<=n;i++)
            {
                pre[i]=i;
                rank1[i]=0;
            }
    }
int find(int x)
    {
        if(pre[x]==x)
            return x;
        else return pre[x]=find(pre[x]);
    }

void unite(int x,int y)
    {
        x=find(x);
        y=find(y);
        if(x==y) return;
        if(rank1[x]<rank1[y])
            {
                pre[x]=y;
            }
        else
            {
                pre[y]=x;
                if(rank1[x]==rank1[y])
                    ++rank1[x];
            }
    }
double krukal()
    {
        sort(es,es+m,comp);
        init(n);
        double res=0;
        for(int i=0;i<m;++i)
            {
                edge e=es[i];
                if(find(e.from)!=find(e.to))
                    {
                        unite(e.from,e.to);
                        res+=e.cost;
                    }
            }
        return res;
    }
double dis(int x1,int y1,int x2,int y2)
    {
        return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
    }
int main()
    {
        while (cin>>n>>m)
            {
                point p[10010];
                int a,b;
                double sum=0;
                for (int i=1;i<=n;++i)
                    {
                        cin>>p[i].x>>p[i].y;
                    }
                for (int i=0;i<m;i++)
                    {

                        cin>>a>>b;
                        es[i].from=a;
                        es[i].to=b;
                        es[i].cost=dis(p[a].x,p[a].y,p[b].x,p[b].y);
                        sum+=es[i].cost;
                    }
                double ans;
                ans=krukal();
                printf("%.3f\n",sum-ans);
            }
    }



Measured memory_bytes: 3864
from math import factorial

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

v.sort(reverse = True)

ans = sum(v[:a]) / a
ans2 = 0

count1 = v.count(v[a-1])

index1 = v.index(v[a-1])

def ncr(x,y):
    return factorial(x) // factorial(y) // factorial(x-y)

if v[0] == v[a-1]:
    for i in range(a, min(b, count1) + 1):
        ans2 += ncr(count1, i)
else:
    ans2 = ncr(count1, a - index1)

print(ans)
print(ans2)


Measured memory_bytes: 3064
import java.util.*;

public class Main {
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		
		int n=sc.nextInt();
	    ArrayList<Integer> a=new ArrayList<>();
	    
	    if(n==1){
	    	System.out.println(sc.nextInt());
			System.exit(0);
	    }
		
	    for(int i=0;i<n;i++){
	    	a.add(sc.nextInt());
	    }
	    Collections.sort(a);
	    
	    if(a.get(a.size()-1)==0){
	    	System.out.println(0);
			System.exit(0);
	    }
	    
	    int ans=0;
	    
	    while(true){
	    	if(a.size()==1){
	    		ans=a.get(0);
	    		break;
	    	}
	    	a=func(a);
	    }
	   System.out.println(ans);
	
	}
	
	private static ArrayList<Integer> func(ArrayList<Integer> A){
		ArrayList<Integer> a=A;
		int min=0;
		for(int i=0;i<a.size();i++){
	    	if(a.get(i)==0){
	    		a.remove(i);
	    		i--;
	    	}else{
	    		if(min!=0){
	    			a.set(i,a.get(i)%min);
	    			if(a.get(i)==1){
	    				System.out.println(1);
	    				System.exit(0);
	    			}
	    		}else{
	    			min=a.get(i);
	    		}
	    	}
	    }
		Collections.sort(a);
		return a;
	}
		
		
}


Measured memory_bytes: 60592
#include <bits/stdc++.h>
using namespace std;
#define all(V) V.begin(),V.end()
using ll = long long;
const ll MOD = 1000000007;

int p, poly[3000], nume[3000], tmp[3000], fc[3000], a[3000];

int modpow(int x, int k) {
	int ans = 1;
	while (k) {
		if (k & 1)ans *= x;
		ans %= p;
		x *= x;
		x %= p;
		k /= 2;
	}
	return ans;
}

int main() {
	cin >> p;

	nume[0] = 1;
	for (int i = 0;i < p;i++) {
		tmp[0] = nume[0] * i;
		for (int j = 1;j <= p;j++) {
			tmp[j] = nume[j - 1] - nume[j] * i;
			tmp[j] %= p;if (tmp[j] < 0)tmp[j] += p;
		}
		for (int j = 0;j <= p;j++) {
			nume[j] = tmp[j];
		}
	}
	
	for (int i = 0;i < p;i++) {
		cin >> poly[i];
	}

	int dom;
	for (int j = 0;j < p;j++) {
		tmp[p] = nume[p];
		for (int i = p - 1;i >= 0;i--) {
			fc[i] = tmp[i + 1] % p;
			tmp[i] = nume[i] + fc[i] * j;
		}

		//分母計算
		dom = 1;
		for (int i = 0;i < p;i++) {
			if (i == j)continue;
			dom *= j - i;
			dom %= p;if (dom < 0)dom += p;
		}
		for (int i = 0;i < p;i++) {
			a[i] += fc[i] * modpow(dom, p - 2) % p * poly[j];
			a[i] %= p;
		}
	}
	for (int i = 0;i < p;i++) {
		cout << a[i];
		if (i == p - 1)cout << endl;
		else cout << " ";
	}
}

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

int main(){
  int N;
  int A[100000];
  int sum = 1;
  int j = 1;
  cin>>N;
  for(int i = 1;i < N+1;i++){
    cin>>A[i];
  }
  while(sum<N+2){
    if(A[j]==2){
      cout<<sum<<endl;
      break;
    }
    j=A[j];
    sum++;
    if(sum ==N+1){
      cout<<-1<<endl;
    }
  }
}

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

#define ll long long
#define INF 99999999
#define INF_LL 1LL << 60
#define MOD (ll)1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rrep(i, n) for(int i = (int)(n); i >= 0; i--)
#define REP(i, a, n) for(int i = a; i < (int)(n); i++)
#define RREP(i, a, n) for(int i = (int)(n); i >= a; i--)
#define all(x) (x).begin(),(x).end()

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; }

void put_double(double obj){printf("%.12f\n",obj);};

template < typename T > std::string to_string( const T& n )
{
    std::ostringstream stm ;
    stm << n ;
    return stm.str() ;
}

ll gcd(ll x, ll y)
{
	return y==0 ? x:gcd(y,x % y);
}

template<typename T> vector<ll> divisor( T n)
{
  vector<ll> ret;
  for(ll i = 1; i * i <= (ll)(n); i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(all(ret));
  return ret;
}

int main()
{
    int A,B,K;
    cin >> A >> B >> K;
    
    int key = gcd(A,B);
    vector<ll> ans = divisor(key);
    reverse(all(ans));
    //rep(i, ans.size()) cout << ans[i] << endl;
    cout << ans[K-1] << endl;

    

}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException
    {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in), 1);
        String s = r.readLine();
        if(s.contains("a") && s.contains("b") && s.contains("c"))
        {
            System.out.println("Yes");
        }
        else
        {
            System.out.println("No");
        }
    }
}


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

int main(){
    string s;
    cin >> s;
    int start, end;
    bool flag=true;
    for(int i=0; i<s.size(); i++){
        if(s[i]=='A'&&flag){
            start = i;
            flag = false;
        }
        if(s[i]=='Z') end = i;
    }
    cout << end-start+1 << endl;
    return 0;
}

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

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, n)  FOR(i, 0, n)
#define ASC(c) sort((c).begin(), (c).end())
#define DESC(c) sort((c).begin(), (c).end(), greater<int>())

#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define DEBUG(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

typedef long long ll;
typedef unsigned long long ull;
struct edge { int u, v; ll w; };
 
ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

int n, m;

int main() {
    cin >> n >> m;
    ll dp[100001] = {0};
    int a[100001] = {0};
    dp[0] = 1;
    REP(i, m) { 
        int tmp; cin >> tmp;
        a[tmp] = 1;
    }
    REP(i, n) {
        if (a[i + 1] == 0) dp[i + 1] += dp[i];
        dp[i + 1] %= MOD;
        if (a[i + 2] == 0) dp[i + 2] += dp[i];
        dp[i + 2] %= MOD;
    }
    cout << dp[n] << endl;
}


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

struct edge{int to,cap,rev;};

const int MAX_V=101*101;
const int INF=INT_MAX/2;
vector<edge> G[MAX_V];
bool used[MAX_V];

void add_edge(int from,int to,int cost){
  G[from].push_back((edge){to,cost,(int)G[to].size()});
  G[to].push_back((edge){from,0,(int)G[from].size()-1});
}

int dfs(int v,int t,int f){
  if(v==t) return f;
  used[v]=1;
  for(int i=0;i<G[v].size();i++){
    edge &e=G[v][i];
    if(!used[e.to] && e.cap>0){
	     int d=dfs(e.to,t,min(f,e.cap));
	      if(d>0){
	         e.cap-=d;
	         G[e.to][e.rev].cap+=d;
	         return d;
	      }
	  }
  }
  return 0;
}

int max_flow(int s,int t){
  int flow=0;
  while(1){
    memset(used,0,sizeof(used));
    int f=dfs(s,t,INF);
    if(f==0) return flow;
    flow+=f;
  }
}

char A[111][111];
bool visit[111][111];

int main(){
  int H,W; cin>>H>>W;
  int sr,sc,tr,tc;
  rep(i,H) rep(j,W){
    cin>>A[i][j];
    if(A[i][j]=='S') sr=i+1,sc=j+1;
    if(A[i][j]=='T') tr=i+1,tc=j+1;
  }
  if(sr==tr||sc==tc){
    cout<<-1<<endl;
    return 0;
  }
  int S=0, T=H+W+1;
  add_edge(S,sr,INF);
  add_edge(S,H+sc,INF);
  add_edge(tr,T,INF);
  add_edge(H+tc,T,INF);
  rep(i,H) rep(j,W) if(A[i][j]!='.'){
    int v=i+1, u=H+j+1;
    add_edge(v,u,1);
    add_edge(u,v,1);
  }
  cout<<max_flow(S,T)<<endl;
  return 0;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
int main() {
    long long int n,i,temp,j,k,sum=0;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            for(k=1;k<=n;k++)
            {
                temp=__gcd(j,k);
                sum=sum+__gcd(temp,i);
            }
        }
    }
    cout<<sum;
    return 0;
}

Measured memory_bytes: 3636
using System;
using System.IO;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Threading.Tasks;
using System.Text.RegularExpressions;
using static System.Math;
using Debug = System.Diagnostics.Debug;


static class P
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        //和が同じになるようなクラスタを構成
        bool isOdd = n % 2 != 0;
        n = (n / 2) * 2;

        List<Tuple<int, int>> edges = new List<Tuple<int, int>>();
        int s = 1 + n;
        for (int i = 1; i <= n / 2; i++)
        {
            int anotherVertex = s - i;
            for (int j = 1; j <= n; j++)
            {
                if (j == i || j == anotherVertex) continue;
                int anotherVert = s - j;
                edges.Add(new Tuple<int, int>(i, j));
                edges.Add(new Tuple<int, int>(i, anotherVert));
                edges.Add(new Tuple<int, int>(anotherVertex, j));
                edges.Add(new Tuple<int, int>(anotherVertex, anotherVert));
            }
        }
        if (isOdd)
        {
            for (int i = 1; i <= n; i++)
            {
                edges.Add(new Tuple<int, int>(i, n + 1));
            }
        }
        edges = edges.Select(x => x.Item1 > x.Item2 ? new Tuple<int, int>(x.Item2, x.Item1) : x).Distinct().ToList();
        Console.WriteLine(edges.Count);
        Console.WriteLine(string.Join("\n", edges.Select(x => $"{x.Item1} {x.Item2}")));
    }
}

Measured memory_bytes: 17244
/*|In The Name Of Allah|*/

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+5;

int n;
int a;
int b;
int ar[N];

int main(){
    scanf("%d" , &n);
    for(int i = 1; i <= n; i++){
        scanf("%d" , &ar[i]);
        if(ar[i] > a)
           a = ar[i];
    }
    sort(ar + 1 , ar + n + 1);
    for(int i = 1; i <= n; i++){
        if(ar[i] == a)
            continue;
        if(ar[i] <= a / 2 && a/2 - ar[i] < a/2 - b){
            b = ar[i];
        } else if( ar[i] >= ((a/2) + (a&1)) && ar[i] - ((a/2) + (a&1)) < abs(b - ((a/2) + (a&1))) ){
            b = ar[i];
        }
    }
    printf("%d %d\n" , a , b);
}


Measured memory_bytes: 640
#![allow(unused_imports)]
#![allow(non_snake_case)]
use proconio::{input, fastout};
use proconio::marker::{Chars, Bytes, Usize1};

#[fastout]
fn main() {
    input!{
        n:usize,
        a:[usize; n]
    }
    let mut cm = 0;
    let mut ans = 0;
    for &x in &a {
        if x < cm {
            ans += cm - x;
        } else {
            cm = x;
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 5612
#include <iostream>
#define REP(i,n) for(int i=0;i<(n);++i)
using namespace std;
typedef long long ll;

// 単純に範囲内の各座標の C を足すのは 10^6まで範囲があるので、 10^12 で全くもってNG
// 工夫して計算量を抑える必要がある。
// ある座標での経路総数を f(x,y) とすると
// 	f(a+1,b) = f(a,0) + f(a,1) +  f(a,2) + ... + f(a,b)
// らしい。
// 	3  ─〇 ← (a+1, 3)
// 	2  ─┤
// 	1  ─┤
// 	0  ─┘
// 	  a  a+1
// となると、(a+1, 4) に行く経路は (a,0),(a,1),(a,2),(a,3) の合計になる。
// ということは求める長方形に上辺の各値を計算したら、その一つ左の列の縦全部を加算した値がわかる。
// 求める長方形の下辺の一個下の各値を計算して引いてやると、長方形の中身の合計がわかる。
// 上辺の各値の加算も、上記のxとyとが逆になった版と考えることができて、
// 上辺の右端+1 までの合計値は、上辺の右端+1をさらに一個上に行った座標の値になる。
// よって範囲が 横 r1 ～ r2、縦 c1 ～ c2 なので、
// 	f(r2+1, c2+1) - f(r1, c2+1) - f(r2+1, c1) + f(r1+1,c1+1)
// で計算できる。

const int MAX = 2000005;
const int MOD = 1000000007;

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

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main() {
  // 前処理
  COMinit();

  ll r1,r2,c1,c2;
  cin >> r1 >> c1 >> r2 >> c2;
  // f(r2+1, c2+1) - f(r1, c2+1) - f(r2+1, c1) + f(r1+1,c1+1)
  ll ans = (COM( r2+1+c2+1, c2+1 ) + COM( r1+c1, c1 )) % MOD;
  ans -= COM( r1+c2+1, c2+1 );
  ans = (ans<0) ? ans + MOD : ans;
  ans -= COM( r2+1+c1, c1 );
  ans = (ans<0) ? ans + MOD : ans;
  cout << ans << endl;
}



Measured memory_bytes: 47104
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
using namespace std;
typedef long long ll;
const ll mod=1000000009;
const ll INF=(ll)1000000007*1000000007;
#define rep(i,n) for(int i=0;i<n;i++)
int main(){
  int N,T; cin >> N >> T;
  int ans=mod;
  rep(i,N){
    int c,t; cin >> c >> t;
    if(t<=T && ans>c){
      ans=c;
    }
  }
  if(ans!=mod){
    cout << ans << endl;
  }
  else{
    cout << "TLE" <<endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <bitset>
#include <functional>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <cmath>
using namespace std;
typedef long long i64;
typedef long double ld;
typedef pair<i64,i64> P;
#define rep(i,s,e) for(int i = (s);i <= (e);i++)

int n;
vector<i64> edges(n + 10, 0);
vector<int> x(n + 10, 0);
vector<int> sum(n + 10, 0);
int result = 0;
void dfs(i64 i, i64 bit, int now_sum) {
  result = max(result, now_sum);
  if (i == n)
    return;
  //枝刈り
  if (now_sum + sum[i] <= result)
    return;
  // throw
  dfs(i + 1, bit, now_sum);

  if (0 == (bit & edges[i]))
    dfs(i + 1, bit | (1LL << i), now_sum + x[i]);
};
int get_i(map<string,int> &mp,string s) {
  mp.emplace(s,mp.size());
  return mp[s];
};

int main(){
    while(cin >> n,n){
        edges.assign(n + 10, 0);
        x.assign(n + 10, 0);
        map<string,int> mp;
        for (int c = 0; c < n; c++) {
          string s;
          cin >> s;
          int i = get_i(mp,s);
          int C;
          cin >> x[i] >> C;
          for (int d = 0; d < C; d++) {
            cin >> s;
            edges[i] |= (1LL << get_i(mp,s));
          }
        }

        sum.assign(n + 10,0);
        for(int i = n - 1;i >= 0;i--){
            sum[i] = sum[i + 1] + x[i];
        }
        result = 0;
        dfs(1,1,x[0]);
        cout << result << endl;
    }
}


Measured memory_bytes: 3184
#include <iostream>
#include <string>
using namespace std;
long long int x;
int main(){
        int n;
        cin >> n;
        string s;
        long long int a[5]={0,0,0,0,0};
        int d[10]={0,0,0,0,0,0,1,1,1,2};
        int d1[10]={1,1,1,2,2,3,2,2,3,3};
        int d2[10]={2,3,4,3,4,4,3,4,4,4};
        for(int i=0; i<n; i++) {
                cin >> s;
                if(s[0]=='M') a[0]++;
                if(s[0]=='A') a[1]++;
                if(s[0]=='R') a[2]++;
                if(s[0]=='C') a[3]++;
                if(s[0]=='H') a[4]++;
        }
        for(int i=0; i<10; i++) {
                x+=(a[d[i]]*a[d1[i]]*a[d2[i]]);
        }
        cout << x<< endl;
}


Measured memory_bytes: 384
while True:
    m, n_min, n_max = map(int, input().split())
    if (m+n_min+n_max) == 0:
        break
    else:
        score = []
        before = 0
        dif = 0
        num = 0
        for i in range(1, m+1):
            s = int(input())
            if n_min+1 <= i <= n_max+1:
                if before - s >= dif:
                    num = i - 1
                    dif = before - s
            before = s
        print(num)



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

int main(){
    string s;
    bool bad = 0;
    cin >> s;

    for(int i = 1; i < s.length(); i++){
        if(bad){
            break;
        }
        if(s[i-1] == s[i]){
            bad = 1;
        }
    }

    if(bad){
        cout << "Bad" << endl;
    }else{
        cout << "Good" << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

#define MAX_N 200005

class UnionFind
{
public:
  int par[MAX_N];
  int depth[MAX_N];
  int nGroup[MAX_N];

  UnionFind(int n) {
    init(n);
  }

  void init(int n) {
    for(int i=0; i<n; i++) {
      par[i] = i;
      depth[i] = 0;
      nGroup[i] = 1;
    }
  }

  int root(int x) {
    if(par[x] == x) {
      return x;
    } else {
      return par[x] = root(par[x]);
    }
  }

  bool same(int x, int y) {
    return root(x) == root(y);
  }

  void unite(int x, int y) {
    x = root(x);
    y = root(y);
    if(x == y) return;

    if(depth[x] < depth[y]) {
      par[x] = y;
      nGroup[y] += nGroup[x];
      nGroup[x] = 0;
    } else {
      par[y] = x;
      nGroup[x] += nGroup[y];
      nGroup[y] = 0;
      if(depth[x] == depth[y])
        depth[x]++;
    }
  }
};
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  vector<ll> X(N), Y(N);
  map<ll, vector<ll>> cntX, cntY;
  rep(i, N) {
    cin >> X[i] >> Y[i];
    cntX[X[i]].push_back(Y[i]);
    cntY[Y[i]].push_back(X[i]);
  }
  map<ll, int> idx, idy;
  {
    int i = 0;
    for(auto x: cntX) {
      idx[x.first] = i;
      i++;
    }
    i = 0;
    for(auto y: cntY) {
      idy[y.first] = i;
      i++;
    }
  }
  UnionFind uf(idy.size());
  for(auto x: cntX) {
    int two = 0;
    for(ll y: x.second) {
      if(cntY[y].size() > 1) two++;
    }
    if(two) {
      for(ll y: x.second) {
        uf.unite(idy[x.second[0]], idy[y]);
      }
    }
  }
  map<int, set<ll>> points;
  map<int, int> cnt;
  for(auto y: cntY) {
    for(ll x: y.second) {
      points[uf.root(idy[y.first])].insert(x);
      cnt[uf.root(idy[y.first])]++;
    }
  }
  ll ans = 0;
  for(auto p: points) {
    ans += (uf.nGroup[p.first] * p.second.size()) - cnt[p.first];
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 26368
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long a,b,c,d;
	cin>>a>>b>>c;
	d=c-a-b;
	if(d>0 && (d*d)>(4*a*b))
	 cout<<"Yes";
	else
	 cout<<"No";
}

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


int main() {
	int N;
	cin >> N;
	string p,q;
	string yes = "#";
	string no = "."; 
	bool flag = false;
	bool last = false;
	while(true) {
		for(int i=0; i<4; i++) {
			string s = p;
			string t = q;
			if(!last) {
				if(i%2==1) s += yes;
				else s += no;
				if(i<=1) t += yes;
				else t += no;
			}
			else {
				if(i%2==1) s = yes + s;
				else s = no + s;
				if(i<=1) t = yes + t;
				else t = no + t;
			}
			cout << s << endl << t << endl;
			fflush(stdout);
			string data;
			cin >> data;
			if(data == "end") {
				flag = true;
				break;
			}
			if(data == "T") {
				p = s;
				q = t;
				break;
			}
			if(data=="F" && i==3) {
				last = true;
			}
		}
		if(flag) break;
	}
	
	
	
	return 0;
}



Measured memory_bytes: 596
#include "bits/stdc++.h"
using namespace std;

#define ASC(vec) vec.begin(), vec.end()		// 昇順ソート 例：sort(ASC(vec));
#define DESC(vec) vec.rbegin(), vec.rend()	// 降順ソート 例:sort(DESC(vec));
#define rep(i, n) for(int i = 0; i < n; i++)
#define Rep(i, n) for(int i = 1; i < n; i++)
#define Ans(s) cout << s << endl

const int mod = 1000000007;
const int inf = (int)1e9 + 7;
const long long INF = 1LL << 60;

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

int GCD(int a, int b) { return b ? GCD(b, a % b) : a; }
int round_int(int a, int b) { return (a + (b - 1)) / b; }

typedef long long ll;
typedef vector<int> inv;

// 4,8方向に探索する際に用いる配列
//int dx[4] = { 0,  0, 1, -1 };
//int dy[4] = { 1, -1, 0,  0 };
//int dx[8] = { 1, 0, -1,  0, 1, -1, -1,  1 };
//int dy[8] = { 0, 1,  0, -1, 1,  1, -1, -1 };

constexpr auto MAX = 100010;

int main()
{
	int d, g;
	cin >> d >> g;

	vector<int> p(d);
	vector<int> c(d);

	rep(i, d) cin >> p[i] >> c[i];

	ll ans = INF;

	rep(bit, (1 << d))
	{
		ll score = 0;
		ll cnt = 0;

		rep(i, d)
		{
			if (bit & (1 << i))
			{
				score += c[i] + p[i] * 100 * (i + 1);
				cnt += p[i];
			}
		}
		if (score >= g) ans = min(ans, cnt);
		else
		{
			for (int i = d - 1; i >= 0; i--)
			{
				if (bit & (1 << i)) continue;
				
				rep(j, p[i])
				{
					if (score >= g) break;
					score += 100 * (i + 1);
					cnt++;
				}
			}
			ans = min(ans, cnt);
		}
	}
	Ans(ans);
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
odd = [A[i] for i in range(0, N) if not(i & 1)]
even = [A[i] for i in range(0, N) if i & 1]
ans = []
if N & 1:
    ans.extend(reversed(odd))
    ans.extend(even)
else:
    ans.extend(reversed(even))
    ans.extend(odd)
print(*ans)


Measured memory_bytes: 25156
import java.util.Scanner;

public class Main  {
    private static Scanner sc= new Scanner(System.in);
    public static void main(String[] args) {
        int n=sc.nextInt();
        double a[]=new double[n];
        for(int i=0;i<n;i++){
            a[i]=sc.nextDouble();
        }

        double s=0;
        for(int i=0;i<n;i++){
            s=s+(1/a[i]);
        }
        s=1/s;
       System.out.print(s);

    }}

Measured memory_bytes: 23124
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
    ll n,x,ans=0;
    cin >> n >> x;
    vector<pair<ll,ll>> v(n);//どの数字が何個か
    vector<ll> sum(n+1);//累積和
    sum.at(0)=0;
    
    for(ll i=0;i < n;i++){
        cin >> v.at(i).first >> v.at(i).second;
    }
    sort(v.begin(),v.end());//数字を昇順にソートして

    for(ll j=0;j < n;j++){
        sum.at(j+1) += sum.at(j)+v.at(j).second;
    }//個数の累積和を取る→何個目かで求める数が定まる

    for(ll k=0;k < n;k++){
        if(sum.at(k) < x && x <= sum.at(k+1)){
            ans = v.at(k).first;
            break;
        }
    }//このforに問題がある（K=nで問題あり？）
    cout << ans << endl;
}

Measured memory_bytes: 2560
import sys

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

A,B,Q = LI()
inf = 10**12
s = [-inf]+[I() for _ in range(A)]+[inf]
t = [-inf]+[I() for _ in range(B)]+[inf]
x = [I() for _ in range(Q)]

from bisect import bisect

# xiより東にある神社・寺の中で最も西にあるもの、xiより西にある神社・寺の中で最も東にあるものだけがあると思えばよい

for i in range(Q):
    y = x[i]
    a = bisect(s,y)
    b = bisect(t,y)
    s1,s2,t1,t2 = s[a-1],s[a],t[b-1],t[b]
    z1 = abs(y-s1)+abs(s1-t1)
    z2 = abs(y-s1)+abs(s1-t2)
    z3 = abs(y-s2)+abs(s2-t1)
    z4 = abs(y-s2)+abs(s2-t2)
    z5 = abs(y-t1)+abs(t1-s1)
    z6 = abs(y-t1)+abs(t1-s2)
    z7 = abs(y-t2)+abs(t2-s1)
    z8 = abs(y-t2)+abs(t2-s2)
    print(min(z1,z2,z3,z4,z5,z6,z7,z8))

Measured memory_bytes: 94688
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <stack>
#include <unordered_map>
#include <queue>
using namespace std;

int main () {
	long long int a, b, k;
	cin >> k >> a >> b;
	if (a + 2 >= b) {
		cout << 1 + k;
		return 0;
	}
	k -= a - 1;
	if (k < 2) {
		cout << a + k;
		return 0;
	}
	cout << a + k + k / 2 * (b - a - 2);
}

Measured memory_bytes: 256
#include <iostream>
#include <utility>
#include <vector>
#include <queue>
#include <stack>
#include <array>
#include <algorithm>
#include <numeric>
#include <limits>
#include <string>
#include <regex>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

int main()
{
    double r;
    cin >> r;
    cout << r * 6.28318530717958623200 << endl;
    return 0;
}


Measured memory_bytes: 3816
#pragma once
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <deque>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
void Sandglass2() {
	int x, t;
	cin >> x >> t;
	cout << max(x - t, 0) << endl;

}
int main() {

	Sandglass2();
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <math.h>
using namespace std;
int main(){
    int h,w,k;
    cin >> h >> w >> k;
    int x1,y1,x2,y2;
    cin >> y1 >> x1 >> y2 >> x2;
    x1--;
    y1--;
    x2--;
    y2--;
    bool c[h*w];
    int pid[h*w];
    int cost[h*w];
    char tt;
    int i,j;
    for(i=0;i<h*w;i++){
        cin >> tt;
        c[i]=(tt=='.') ? true : false;
        cost[i]=-1;
    }
    pid[0]=y1*w+x1;
    cost[y1*w+x1]=0;
    int nc=1;
    int xn,yn,xp,yp;
    for(i=0;i<nc;i++){
        xn=pid[i]%w;
        yn=pid[i]/w;
        for(yp=yn-1;yp>=0&& yn-yp<=k;yp--){
            if(c[yp*w+xn]==false)break;
            if(cost[yp*w+xn]==cost[pid[i]])break;
            if(cost[yp*w+xn]>=0)continue;//check
            pid[nc]=yp*w+xn;
            cost[yp*w+xn]=cost[pid[i]]+1;
            nc++;
            if(x2==xn&&y2==yp){
                cout << cost[pid[i]]+1 << endl;
                return 0;
            }
        }
        for(xp=xn-1;xp>=0&& xn-xp<=k;xp--){
            if(c[yn*w+xp]==false)break;
            if(cost[yn*w+xp]==cost[pid[i]])break;
            if(cost[yn*w+xp]>=0)continue;//check
            pid[nc]=yn*w+xp;
            cost[yn*w+xp]=cost[pid[i]]+1;
            nc++;
            if(x2==xp&&y2==yn){
                cout << cost[pid[i]]+1 << endl;
                return 0;
            }
        }
        for(yp=yn+1;yp<h&& yp-yn<=k;yp++){
            if(c[yp*w+xn]==false)break;
            if(cost[yp*w+xn]==cost[pid[i]])break;
            if(cost[yp*w+xn]>=0)continue;//check
            pid[nc]=yp*w+xn;
            cost[yp*w+xn]=cost[pid[i]]+1;
            nc++;
            if(x2==xn&&y2==yp){
                cout << cost[pid[i]]+1 << endl;
                
                return 0;
            }
        }
        for(xp=xn+1;xp<w&& xp-xn<=k;xp++){
            if(c[yn*w+xp]==false)break;
            if(cost[yn*w+xp]==cost[pid[i]])break;
            if(cost[yn*w+xp]>=0)continue;//check
            pid[nc]=yn*w+xp;
            cost[yn*w+xp]=cost[pid[i]]+1;
            nc++;
            if(x2==xp&&y2==yn){
                cout << cost[pid[i]]+1 << endl;
                return 0;
            }
        }
    }
    cout << -1 << endl;

    return 0;
}

Measured memory_bytes: 10760
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep_range(i, s, e) for (int i = (s); i < (int)(e); i++)
#define rep_rev(i, s, e) for (int i = (s)-1; i >= (int)(e); i--)
#define sort_vec(v) sort((v).begin(),(v).end())
typedef int64_t lint;
// lint mod = 998244353;

lint app() {
  string s;
  cin>>s;
  int n=s.length();

  lint out=0;
  vector<vector<lint>> count(2,vector<lint>(2019,0));
  rep(i,n){
    count[1-i%2][0]+=1;
    int a=s[i]-'0';
    rep(r,2019){
      count[i%2][(r*10+a)%2019]=count[1-i%2][r];
    }
    out+=count[i%2][0];
  }

  return out;
}

int main(){cout<<app()<<endl;return 0;}


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

int main()
{
	int n;
	int countR = 0, countB = 0;
	string input;

	cin >> n;

	cin >> input;

	for( int i = 0; i < n; i++){
		if(input[i] == 'R'){
			countR++;
		} else if(input[i] == 'B'){
			countB++;
		}
	}
	if(countR > countB){
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}

	return 0;
}

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

using namespace std;

typedef long long int ll;

const int N = (int) 3e3 + 10;
const int oo = 987654321;

int n, m;
string s, t;
int memo[N][N];

int dp(int i, int j) {
    if(i > n || j > m) return -oo;
    if(i == n && j == m) return 0;
    int &ans = memo[i][j];
    if(ans != -1) return ans;
    if(s[i] == t[j]) {
        ans = max(ans, 1 + dp(i + 1, j + 1));
    }
    ans = max(ans, dp(i + 1, j));
    ans = max(ans, dp(i, j + 1));
    return ans;
}

string go(int i, int j) {
    if(i == n && j == m) return "";
    int actual = dp(i, j);
    if(s[i] == t[j] && 1 + dp(i + 1, j + 1) == actual) {
        return s[i] + go(i + 1, j + 1);
    }
    if(dp(i + 1, j) == actual) return go(i + 1, j);
    if(dp(i, j + 1) == actual) return go(i, j + 1);
    throw;
}

void solve() {
    cin >> s >> t;
    n = s.length(), m = t.length();
    memset(memo, -1, sizeof(memo));
    cout << go(0, 0) << endl;
}

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

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

typedef long long lint;

lint dp[100010][2];
int a[100010],n;

int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++) scanf("%d",&a[i]);
	dp[0][1]=-1e9-1;
	dp[0][0]=0;
	for(int i=0;i<n;i++){
		dp[i+1][0]=max(dp[i][0]+a[i],dp[i][1]-a[i]);
		dp[i+1][1]=max(dp[i][0]-a[i],dp[i][1]+a[i]);
	}
	printf("%lld",dp[n][0]);
	return 0;
}

Measured memory_bytes: 2176
#include "bits/stdc++.h"
using namespace std;

#define ul unsigned long int
#define ull unsigned long long
#define li long long int


int main()
{
  ul x;
  cin>>x;
  for (ul i=1;x>0;i++) {
    cout << "Case " << i <<": "<<x<<endl;
    cin>>x;
  }

  return 0;
}



Measured memory_bytes: 3096
while True:
    try:
        n, r = map(int, input().split())
        cc = list(map(int, input().split()))
        card = [v for v in range(n)]
        for c in cc:
            A, B, C = card[n//2:], card[:n//2], []
            while len(A) or len(B):
                C += A[:c]
                del A[:c]
                C += B[:c]
                del B[:c]
            card = C
        print(C[-1])
    except: break

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

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back

typedef long long ll;
typedef pair<int, int> pi;

string s;
int n;
const int maxn = 3005;
int a[maxn], b[maxn];
string dp[maxn];
bool vis[maxn * 2];

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    cin >> s;
    int n1 = 0, n2 = 0;
    for(int i = 0;i < 2 * n;i++){
        if(s[i] == 'a'){
            a[++n1] = i;
        }else{
            b[++n2] = i;
        }
    }
    for(int i = 0;i < maxn;i++){
        dp[i] = "";
    }
    for(int i = n;i >= 1;i--){
        if(a[i] < b[i]){
            int j = i;
            while(j <= n and (a[j] < b[i])){
                j++;
            }
            dp[i] = "ab" + dp[j];
        }else{
            memset(vis, false, sizeof(vis));
            int r = a[i], j = i;
            while(j <= n and b[j] <= r){
                vis[a[j]] = true;
                vis[b[j]] = true;
                r = max(r, a[j]);
                j++;
            }
            for(int k = 0;k < 2 * n;k++){
                if(vis[k])
                    dp[i].push_back(s[k]);
            }
            dp[i] += dp[j];
        }
        dp[i] = max(dp[i], dp[i + 1]);
    }
    cout << dp[1] << endl;
    return 0;
}


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

int main()
{
  int64_t N, C, ans = 0;
  cin >> N >> C;
  vector<int64_t> xa(N), xb(N), va(N), vb(N), sva(N + 1, 0), svb(N + 1, 0);
  for (int i = 0; i < N; i++)
  {
    cin >> xa.at(i) >> va.at(i);
  }
  for (int i = 0; i < N; i++)
  {
    xb[i] = (C - xa[i]);
    vb[i] = va[i];
  }
  reverse(xb.begin(), xb.end());
  reverse(vb.begin(), vb.end());
  for (int i = 1; i <= N; i++)
  {
    sva[i] = sva[i - 1] + va[i - 1];
    svb[i] = svb[i - 1] + vb[i - 1];
  }
  for (int i = 1; i <= N; i++)
  {
    sva[i] -= xa[i - 1];
    svb[i] -= xb[i - 1];
  }
  int64_t mxa = -(1LL << 62), mxb = -(1LL << 62);
  vector<int64_t> mxsva(N + 1), mxsvb(N + 1);
  for (int i = 1; i <= N; i++)
  {
    mxa = mxsva[i] = max(mxa, sva[i]);
    mxb = mxsvb[i] = max(mxb, svb[i]);
  }
  // pattern 1 & pattern 2
  ans = max(ans, mxsva[N]);
  ans = max(ans, mxsvb[N]);
  // 時計回り -> 反時計回り
  for (int i = 1; i <= N - 1; i++)
  {
    ans = max(ans, sva[i] - xa[i - 1] + mxsvb[N - i]);
  }
  // 反時計回り -> 時計回り
  for (int i = 1; i <= N - 1; i++)
  {
    ans = max(ans, svb[i] - xb[i - 1] + mxsva[N - i]);
  }
  cout << ans << endl;
}


Measured memory_bytes: 9576
#include <cstdio>

#define min(a, b) (a < b ? a : b)

int main()
{
    int no_of_paths, max_time;
    scanf("%d %d", &no_of_paths, &max_time);

    const int oo = 1e9 + 9;
    int min_cost = oo;

    while(no_of_paths--)
    {
        int cost, time;
        scanf("%d %d", &cost, &time);

        if(time <= max_time) min_cost = min(min_cost, cost);
    }

    printf(min_cost == oo ? "TLE\n" : "%d\n", min_cost);
    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rapido ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"

void solve()
{
   int k;
	cin >> k;
	int num = 7;
	if(k % 2 == 0 or k % 5 == 0)
	{
		cout << -1 << endl;
		return;
	}
	for(int i = 1;i <= k;++i)
	{
		if(num % k == 0)
		{
			cout << i << endl;
			return;
		}
		num = (10 * num  + 7) % k;
	}
	return;
    
}
int32_t main()
{
    rapido;
    int t;
    //cin>>t;
      t=1;
    while(t--)
    solve();
}

Measured memory_bytes: 3668
fun readString() = readLine()!!
fun readInt() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readIntList() = readLine()!!.split(" ").map(String::toInt)
fun readLongList() = readLine()!!.split(" ").map(String::toLong)
fun <T> Array<Array<T>>.print() {
    this.forEach {
        println(it.joinToString(" "))
    }
}

fun main() {
    val (s, w) = readIntList()
    println(
        if (s <= w) {
            "unsafe"
        } else {
            "safe"
        }
    )
}


Measured memory_bytes: 36500
from itertools import permutations
import sys
def main():
    N, M, R = map(int, input().split())
    rs = [x - 1 for x in map(int, input().split())]
    # グラフを作る
    dist = [[float('inf')] * (N) for _ in range(N)]
    for e in sys.stdin:
        A, B, C = map(int, e.split())
        dist[A - 1][B - 1] = dist[B - 1][A - 1] = C
    # ワーシャルフロイドで全頂点間距離算出
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    # 組み合わせ全探索
    ans = float('inf')
    for p in permutations(rs):
        tmp = 0
        for u, v in zip(p, p[1:]):
            tmp += dist[u][v]
            if tmp > ans:
                break
        else:
            ans = tmp
    print(ans)
if __name__ == '__main__':
    main()

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

struct Edge {
  int to, id;
};

// adjacant list
vector< vector<Edge> > g;
vector<int> ans;

void dfs(int v, int c=-1, int p=-1) {
  int k = 1;
  rep (i, g[v].size()) {
    int u = g[v][i].to, ei = g[v][i].id;
    if (u == p) continue;
    if (k == c) ++k;
    ans[ei] = k; ++k;
    dfs(u, ans[ei], v);
  }
}

int main() {
  int N;
  cin >> N;
  g.resize(N);
  ans = vector<int>(N);
  rep (i, N - 1) {
    int a, b;
    cin >> a >> b;
    --a; --b;
    g[a].push_back((Edge){b, i});
    g[b].push_back((Edge){a, i});
  }
  dfs(0);
  int mx = 0;
  rep (i, N) mx = max(mx, int(g[i].size()));
  cout << mx << endl;
  rep (i, N - 1) {
    cout << ans[i] << endl;
  }
  return 0;
}


Measured memory_bytes: 8320
n = int(input())
nums = [int(input()) for i in range(n)]
prime_num = 0

def prime(n):
    q = abs(n)
    if q==2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1


for i in nums:
    if(prime(i)):
        prime_num += 1

print(prime_num)



Measured memory_bytes: 5980
#include<stdio.h>
int main(void)
{
   int a,b,d,r;
	double f;
	scanf("%d %d",&a,&b);
	d = (int)(a/b);
	r = a%b;
	f = (double)(a)/(double)(b);
	
	printf("%d %d %.5f\n",d,r,f);
	return 0;
}

Measured memory_bytes: 640