akhauriyash/Code-Regression huggingface dataset:
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] numbers = new long[n];
        int count2xButNot4x = 0;
        int count4x = 0;
        for (int i = 0; i < n; i++) {
            long num = sc.nextLong();
            if (num % 4 == 0) {
                count4x++;
            } else {
                if (num % 2 == 0) {
                    count2xButNot4x++;
                }
            }
            numbers[i] = num;
        }
        
        boolean pass = false;
        if (count2xButNot4x < 2) {
            if (count4x >= n / 2) {
                pass = true;
            }
        } else {
            if (count4x >= (n - count2xButNot4x + 1) / 2) {
                pass = true;
            }
        }
        
        if (pass) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 48780
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
void solve()
{
    int n;
    int m;
    cin>>n>>m;
    int a[n],b[m];
    for(int i=0; i<n; i++)
    {
        cin>>a[i];
    }
    for(int i=0; i<m; i++)
    {
        cin>>b[i];
    }
    sort(a,a+n);
    int p=0;
    for(int i=0; i<m; i++)
    {
        cout<<upper_bound(a,a+n,b[i])-a<<' ';
    }
}
void abc()
{
    ll a[3],b[3];
    for(int i=0; i<3; i++)
        cin>>a[i];
    for(int i=0; i<3; i++)
        cin>>b[i];
    ll sum=0;
    if(a[2]>=a[1])
        sum+=(2*min(a[2],b[1]));
    a[2]-=min(a[2],b[1]);
    b[1]-=min(a[2],b[1]);
    a[1]-=(min(a[1],b[1]));
    a[1]-=(min(a[1],b[0]));
    b[2]-=(min(b[2],a[2]));
    b[2]-=(min(b[2],a[0]));
    if(b[2]>0&&a[1]>0)
    {
        sum-=(2*min(a[1],b[2]));
    }
    cout<<sum<<endl;
}
ll without( ll n)
{
    ll sum=0,i=1;
    while(n>0)
    {
        int d=n%10;
        n/=10;
        if(d==0)
            continue;
        sum+=(i*d);
        i*=10;
    }
    return sum;
}
void bc()
{
    int d,t,s;
    cin>>d>>t>>s;
    if(t*s>=d)cout<<"Yes\n";
    else cout<<"No\n";
}
int main()
{
    ///int t;cin>>t;while(t--){
        bc();


}


Measured memory_bytes: 3568
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        final Scanner sc = new Scanner(System.in);

        final String s = sc.next();

        int ans = 700;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'o') ans += 100;
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 21716
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

int main()
{
  int n;
  cin >> n;
  vector<ll> vs(n + 1);
  fill(vs.begin(), vs.end(), 0);

  for(int i = 2; i <= n; i++) {
    int v = i;
    for(int j = 2; j <= i && v > 1; j++) {
      while(v % j == 0) {
        vs[j]++;
        v /= j;
      }
    }
  }
  ll count = 1;
  for(int i = 2; i <= n; i++) {
    if(vs[i] > 0) {
      count *= (vs[i] + 1);
      count %= 1000000007;
    }
  }
  cout << count << endl;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int dxy[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};

int main(){
  int N;
  int n;
  int d;
  int w, h;
  int box[200][2];
  while(cin >> N, N){
    w = 1;
    h = 1;
    box[0][0] = 0;
    box[0][1] = 0;
    for(int i=1; i<N; i++){
      cin >> n >> d;
      box[i][0] = box[n][0] + dxy[d][0];
      box[i][1] = box[n][1] + dxy[d][1];
    }
    int minw = 60000;
    int maxw = -60000;
    int minh = 60000;
    int maxh = -60000;
    for(int i=0; i<N; i++){
      if(minw > box[i][0]){
	minw = box[i][0];
      }
      if(maxw < box[i][0]){
	maxw = box[i][0];
      }
      if(minh > box[i][1]){
	minh = box[i][1];
      }
      if(maxh < box[i][1]){
	maxh = box[i][1];
      }
    }
    w = maxw - minw + 1;
    h = maxh - minh + 1;
    
    cout << w << " " << h << endl;
  }
  return 0;
}

Measured memory_bytes: 1160
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <iostream>
#include <set>
#include <map>

using namespace std;

class UnionFind {
public:
    vector <int> parent;
    vector <int> size;

    UnionFind(int size_) : parent(size_), size(size_, 1) {
        for (int i = 0; i < size_; ++i) parent[i] = i;
    }

    int root(int x) {
        while (parent[x] != x) {
            x = parent[x] = parent[parent[x]];
        }

        return x;
    }

    bool merge(int x, int y) {
        x = root(x);
        y = root(y);

        if (x == y) return  false;

        if (size[x] < size[y]) swap(x, y);

        size[x] += size[y];
        parent[y] = x;
        return true;
    }

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

    int getSize(int x) {
        return size[root(x)];
    }
};

struct xCmp {
    bool operator() (const pair<int, int>& l, const pair<int, int>& r) const{
        return l.first < r.first;
    }
};

int main() {
    int n;

    scanf("%d", &n);
    vector< pair<int, int> > points;
    set< pair<int, int>, xCmp> xs;
    set< pair<int, int>, xCmp> ys;
    UnionFind uf(n);

    for (int i = 0; i < n; ++i) {
        int x, y;

        scanf("%d%d", &x, &y);

        points.push_back(make_pair(x, y));

        auto it = xs.find(make_pair(x, i));

        if (it != xs.end()) {
            uf.merge(i, it->second);
        }

        xs.insert(make_pair(x, i));

        it = ys.find(make_pair(y, i));

        if (it != ys.end()) {
            uf.merge(i, it->second);
        }
        ys.insert(make_pair(y, i));
    }

    map< int, int > treePoints;
    map< int, set<int> > xCnts;
    map< int, set<int> > yCnts;

    for (int i = 0; i < n; i++) {
       int r = uf.root(i);

       if (!treePoints.count(r)) {
           treePoints[r] = 0;
           xCnts[r] = set<int>();
           yCnts[r] = set<int>();
       }

       treePoints[r] += 1;
       xCnts[r].insert(points[i].first);
        yCnts[r].insert(points[i].second);
    }

    long long res = 0;

    for(auto it = treePoints.begin(); it != treePoints.end(); it++) {
        int key = it->first;

        res += (long long)(xCnts[key].size() * yCnts[key].size() - treePoints[key]);
    }

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

    return 0;
}

Measured memory_bytes: 11252
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <functional>
#include <bitset>
#include <cmath>
#include <stack>
#include <iomanip>
#include <map>
#include <math.h>
#include <list>
#include <deque>
typedef long long ll;
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int MOD = 1000000007;
const ll INF = 1LL << 60;

ll GCD(ll a, ll b) { return b ? GCD(b, a%b) : a; }
ll LCM(ll a, ll b) {return a / GCD(a, b) * b;}

ll dp[110][100010];

int main()
{
	string T;
	cin >> T;
	for(int i = 0; i < T.size(); i++)
	{
		if(T[i] == '?') T[i] = 'D';
	}
	cout << T << endl;
}


Measured memory_bytes: 3488
#include<stdio.h>
int main(){
  int A[1000],i,j,N,v,k;
  scanf("%d",&N);
  for(i=0;i<N;i++) scanf("%d",&A[i]);
  for(k=0;k<N-1;k++) printf("%d ",A[k]);
  printf("%d\n",A[k]);
  
  for(i=1;i<N;i++){
    v=A[i];
    j=i-1;
    while(j>=0 && A[j]>v){
      A[j+1]=A[j];
      j--;
      A[j+1]=v;
    }
    for(k=0;k<N-1;k++) printf("%d ",A[k]);
    printf("%d\n",A[k]);
  }
  return 0;
}



Measured memory_bytes: 2140
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <bitset>
#include <set>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define all(i,n) (i),(i+n)

int dx4[4]={1,0,-1,0};
int dy4[4]={0,-1,0,1};
int dx8[8]={1,0,-1,1,-1,1,0,-1};
int dy8[8]={1,1,1,0,0,-1,-1,-1};

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

const int INF = 1e9;
const ll LLINF = 1e18;
const int MAX_V = 1e6+1;
const ll mod = 1000000007;

// --------------------------------------
int h, w;
string g[2001];

int search_w(int x, int y) {
  int sum = 0;
  FOR(i, y, w) {
    if(g[x][i] == '#') break;
    else sum++;
  }
  return sum;
}

int search_h(int x, int y) {
  int sum = 0;
  FOR(i, x, h) {
    if(g[i][y] == '#') break;
    else sum++;
  }
  return sum;
}

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

  cin >> h >> w;
  REP(i, h) cin >> g[i];

  int hdp[2001][2001];
  int wdp[2001][2001];

  REP(i, h) {
    REP(j, w) {
      if(g[i][j] == '#') {
        wdp[i][j] = -1;
      } else {
        if(j == 0 || wdp[i][j - 1] == -1) wdp[i][j] = search_w(i, j);
        else wdp[i][j] = wdp[i][j - 1];
      }
    }
  }

  REP(i, w) {
    REP(j, h) {
      if(g[j][i] == '#') {
        hdp[j][i] = -1;
      } else {
        if(j == 0 || hdp[j - 1][i] == -1) hdp[j][i] = search_h(j, i);
        else hdp[j][i] = hdp[j - 1][i];
      }
    }
  }

  int ans = 0;
  REP(i, h) {
    REP(j, w) {
      if(g[i][j] == '.') {
        ans = max(ans, wdp[i][j] + hdp[i][j] - 1);
      }
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 35840
import math
K = int(input())
N = 0
 
for a in range(1,K+1):
    for b in range(a,K+1):
        for c in range(b,K+1):
            g = math.gcd(a,b)
            g = math.gcd(g,c)
            if(a != b or a != c):
                if(a != b and a != c and b != c):
                    g *= 6
                else:
                    g *= 3
            N += g
 
print(N)

Measured memory_bytes: 70392
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#pragma GCC optimize("Os")
#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);
#define FO cout.tie(NULL);
#define FI cin.tie(NULL);
#define IN cin>>
#define OUT cout<<
#define loop(i,a,n) for(int i=a; i<n; i++)
#define rloop(i,a,n) for(int i=a; i>=n; i--)
#define endl "\n";
#define pb push_back
#define mp make_pair
#define set_bits(a) __builtin_popcountll(a)
#define ll long long int
#define ld long double
#define vll vector<long long int>
#define pll pair<long long int, long long int>
#define mod 1000000007
#define M 998244353
using namespace std;
ll gcd(ll a, ll b)
{
    return (b?gcd(b,a%b):a);
}
ll P(ll B, ll power, ll modulo)
{
    ll ans=1LL;
    while(power>0LL)
    {
        if(power%2LL==1LL)
        {
            ans=(ans*B)%modulo;
        }
        B=(B*B)%modulo;
        power/=2LL;
    }
    return ans;
}
bool isPrime(ll n)
{
    if(n<=1LL)
    {
        return false;
    }
    if(n<=3LL)
    {
        return true;
    }
    if(n%2==0LL || n%3==0LL)
    {
        return false;
    }
    for(ll i=5LL; (i*i)<=n; i+=6LL)
    {
        if(n%i==0LL || n%(i+2LL)==0LL)
        {
            return false;
        }
    }
    return true;
}
void vok()
{
    FAST
    FO
    FI
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
        freopen("error.txt","w",stderr);
    #endif
}
int main()
{
    vok();
    int n;
    IN n;
    map<string,int> m;
    loop(i,0,n)
    {
        string s;
        IN s;
        m[s]++;
    }
    OUT "AC x "<<m["AC"]<<endl
    OUT "WA x "<<m["WA"]<<endl
    OUT "TLE x "<<m["TLE"]<<endl
    OUT "RE x "<<m["RE"]<<endl
    return 0;
}

Measured memory_bytes: 3660
c = [list(map(int, input().split())) for _ in range(3)]
dif_1 = c[0][1] - c[0][0]
dif_2 = c[0][2] - c[0][1]
dif_3 = c[1][0] - c[0][0]
dif_4 = c[2][0] - c[1][0]

if c[1][1] - c[1][0] != dif_1 or c[2][1] - c[2][0] != dif_1:
    print("No")
    exit()
elif c[1][2] - c[1][1] != dif_2 or c[2][2] - c[2][1] != dif_2:
    print("No")
    exit()
elif c[1][1] - c[0][1] != dif_3 or c[1][2] - c[0][2] != dif_3:
    print('No')
    exit()
elif c[2][2] - c[1][2] != dif_4 or c[2][1] - c[1][1] != dif_4:
    print('No')
    exit()
print('Yes')

Measured memory_bytes: 3064
def dfs(i, f):
  if i == n - 1:
    return sum(list(map(int, f.split('+'))))
  
  return dfs(i + 1, f + s[i + 1]) + dfs(i + 1, f + '+' + s[i + 1])

s = input()
n = len(s)
print(dfs(0, s[0]))

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
#define all(x) (x).begin(), (x).end()
ll inf = LLONG_MAX;
long double pi = M_PI;
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}

int main() {
  ll a, b;
  cin >> a >> b;

  ll x = ceil(a / 0.08), y = ceil(b / 0.1);
  ll ans = min(x, y);
  while (1) {
    if (floor((double)ans * 0.08) == a && floor((double)ans * 0.1) == b) {
      cout << ans << endl;
      break;
    }
    if (floor((double)ans * 0.08) > a && floor((double)ans * 0.1) > b) {
      cout << -1 << endl;
      break;
    }
    ans++;
  }
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<vector>
#include<list>
#include<functional>
#include<algorithm>
#include<string>
#include<cmath>
#include<complex>
#include<set>
#include<map>
#include<stack>
#include<queue>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;



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

	int N, A, B;
	cin >> N >> A >> B;
	cout << min(A, B) << " " << max(0, A + B - N) << "\n";
	
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n, idx, i, j, k, ans,curr;
    scanf("%d",&n);
    if(n == 3 || n == 5 || n == 7)
        printf("YES\n");
    else
        printf("NO\n");
    return 0;
}


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

using namespace std;

int main(void)
{
    int a, b, c, d;

    cin >> a >> b >> c >> d;

    int turn_count1, turn_count2;
    turn_count1 = int(ceilf((float) c / b));
    turn_count2 = int(ceilf((float) a / d));

    if (turn_count1 <= turn_count2) cout << "Yes";
    else cout << "No";

    return 0;
}


Measured memory_bytes: 3596
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
typedef long long  ll;
#define rep(i,s,n)for(ll i=s;i<n;i++)
#define repe(i,s,n)for(ll i=s;i<=n;i++)

bool a[100005] = {};
bool b[4][100005] = {};
int main() {
	ll n; string s; cin >> n >> s;

	rep(i, 0, s.size())	a[i] = ((s[i] == 'o') ? true : false);
	a[n] = a[0];
	a[n + 1] = a[1];

	b[0][0] = 1; b[0][1] = 1; // SS
	b[1][0] = 1; b[1][1] = 0; // SW
	b[2][0] = 0; b[2][1] = 1; // WS
	b[3][0] = 0; b[3][1] = 0; // WW
	rep(i, 0, 4) {
		rep(j, 1, n + 2) {
			if (b[i][j]) {
				if (a[j]) b[i][j + 1] = b[i][j - 1];
				else  b[i][j + 1] = !b[i][j - 1];
			}
			else {
				if (a[j]) b[i][j + 1] = !b[i][j - 1];
				else  b[i][j + 1] = b[i][j - 1];
			}
		}

		if (b[i][n] == b[i][0] && b[i][n + 1] == b[i][1]) {
			rep(j, 0, n) cout << (b[i][j] ? 'S' : 'W');
			cout << endl;
			return 0;
		}
	}
	cout << -1 << endl;

	return 0;
}

Measured memory_bytes: 1024
#include <iostream>

using namespace std;

int main() {
    long long N, W;
    cin >> N >> W;

    long long V = 1000 * N;

    long long v[N], w[N];
    for (int i = 0; i < N; ++i) {
        cin >> w[i] >> v[i];
    }

    bool dp[2 * V + 1][N + 1];
    long long ws[2 * V + 1];
    for (int i = 0; i < 2 * V + 1; ++i) {
        ws[i] = W + 1;
    }
    ws[0] = 0;

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

    for (int i = 0; i < V; ++i) {
        for (int j = 0; j < N; ++j) {
            if (!dp[i][j] and ws[i] + w[j] < ws[i + v[j]]) {
                for (int k = 0; k < N; ++k) {
                    dp[i + v[j]][k] = dp[i][k];
                }
                dp[i + v[j]][j] = true;
                ws[i + v[j]] = ws[i] + w[j];
            }
        }
    }

    for(int i = V; i >= 0; --i) {
        if(ws[i] <= W) {
            cout << i;
            break;
        }
    }

    return 0;
}

Measured memory_bytes: 12032
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <random>
#include <cstdio>
#include <cstring>
#include <cmath>

// for i in f..<t {... : as Swift
#define forin(i, f, t) for(auto i = f; i < t; i++)

using namespace std;
using ll = long long;

int main() {
    int n;
    cin >> n;
    vector<int> p(n);
    for (auto &v : p)
        cin >> v;
    
    vector<int> dp(n + 2, 0);
    auto Max = 0;
    for (auto i = 0; i < n; i++) {
        dp[p[i]] = dp[p[i] - 1] + 1;
        Max = max(Max, dp[p[i]]);
    }
    
    dp.assign(n + 2, 0);
    for (auto i = n; i > 0; i--) {
        dp[p[i - 1]] = dp[p[i - 1] + 1] + 1;
        Max = max(Max, dp[p[i - 1]]);
    }
    
    cout << n - Max << endl;
    
    return 0;
}



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

int a, b, c;

bool conti(int x, int y, int z){
  if(x % 2 == 0 && y % 2 == 0 && z % 2 == 0){
    return true;
  }
  else{
    return false;
  }
}

int main(){
  cin >> a >> b >> c;
  
  int ans = 0;
  while(true){
    if(!conti(a, b, c)){
      break;
    }
    else if(a == b && b == c){
      ans = -1;
      break;
    }
    else{
      int x, y, z;
      x = (b + c) / 2;
      y = (c + a) / 2;
      z = (a + b) / 2;
      a = x;
      b = y;
      c = z;
      ans++;
    }
  }
  cout << ans << endl;
}


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

int main(){
    string s;
    cin>>s;
    int ans=0;
    if(s.size()%2==1){
        rep(i, (s.size()-1)/2){
            if(s[i]!=s[s.size()-i-1]) ans++;
        }
    }else{
        rep(i, s.size()/2){
            if(s[i]!=s[s.size()-i-1]) ans++;
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3604
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <math.h>
#include <complex>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <bitset>
#include <functional>
#include <assert.h>
#define int long
#define ll long long
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define eb emplace_back
#define all(x) x.begin(),x.end()
#define SZ(x) x.size()
#define fi first
#define se second
const int INF = 1e9;
const int MOD = 1e9+7;
using namespace std;

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

using pi=pair<int,int>;
using vi=vc<int>;

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

    int H,W,K; cin >> H >> W >> K;
    int d[H+1][W];
    rep(i,H+1){
        rep(j,W){
            d[i][j]=0;
        }
    }
    d[0][0]=1;
    rep(i,H){
        rep(j,1<<(W-1)){
            bool frag=false;
            rep(k,W-2){
                if(j>>k&1 && j>>(k+1)&1) frag=true;
            }
            if(frag) continue;
            int w[W];
            rep(k,W){
                w[k]=k;
            }
            rep(k,W-1){
                if(j>>k&1){
                    swap(w[k],w[k+1]);
                } 
            }
            rep(k,W){
                d[i+1][k]=(d[i+1][k]+d[i][w[k]])%MOD;
            }
        }
    }
    cout << d[H][K-1] << endl;
}

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

int main() {
  int D, G, maxdgt, cnt, acm, rest, ans=1000; cin >> D >> G;
  vector<int> P(D,0); vector<int> C(D,0);
  for (int i = 0; i<D; i++) cin >> P[i] >> C[i];
  
  for (int bit = 0; bit < (1<<D); bit++) {
    maxdgt = -1; cnt = 0; rest = G;
    for(int i = 0; i<D; i++) {
      if(bit & (1<<i)) {rest -= P[i]*(i+1)*100+C[i]; cnt +=P[i];}
      else maxdgt = i;
    }
    if(rest <= 0) ans = min(ans, cnt);
    else if((P[maxdgt]-1)*(maxdgt+1)*100<rest) continue;
    else ans = min(ans, cnt +(rest/100-1) / (maxdgt+1) + 1);
  }
  cout << ans << "\n";
}

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

int main(){
	double v,t,y,ans;
	while(cin>>v){
		ans=1;
		t=v/9.8;
		y=4.9*t*t;
		while(y>5*ans-5)ans++;
		cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 1276
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll cnt[100002];

int main()
{
    ll n,nth,sum,ans,i,j;
    scanf("%lld",&n);
    j=1;
    if(!(n&1))
    {
        while(!(n&1))
        {
            cnt[j]++;
            n/=2;
        }
        j++;
    }
    for(i=3; i*i<=n; i+=2)
    {
        if(n%i==0)
        {
            while(n%i==0)
            {
                cnt[j]++;
                n/=i;
            }
            j++;
        }
    }
    if(n>1)cnt[j]++,j++;
    ans=0;
    for(i=1; i<j; i++)
    {
        sum=cnt[i]*2;
        nth=(-1+sqrt(1+4*sum))/2;
        ans+=nth;
    }
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 3792
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getString() string {
	sc.Scan()
	return sc.Text()
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func asub(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

func abs(a int) int {
	if a > 0 {
		return a
	}
	return -a
}

func calc(x, y, z, i int) int {
	ret := 0
	if i%2 == 0 {
		ret += x
	} else {
		ret -= x
	}
	i /= 2
	if i%2 == 0 {
		ret += y
	} else {
		ret -= y
	}
	i /= 2
	if i%2 == 0 {
		ret += z
	} else {
		ret -= z
	}
	return ret
}

func main() {
	sc.Split(bufio.ScanWords)

	N, M := getInt(), getInt()
	x := make([]int, N)
	y := make([]int, N)
	z := make([]int, N)
	for i := 0; i < N; i++ {
		x[i], y[i], z[i] = getInt(), getInt(), getInt()
	}

	ans := 0
	for i := 0; i < 8; i++ {
		a := make([]int, N)
		for j := 0; j < N; j++ {
			a[j] = calc(x[j], y[j], z[j], i)
		}
		sort.Ints(a)
		sum := 0
		for j := 0; j < M; j++ {
			sum += a[N-1-j]
		}
		ans = max(ans, sum)
	}
	out(ans)
}


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

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repr(i, n) for(int i = (n-1); i >= 0; --i)

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

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

const int MAX = 200005;
const int INF = 1001001001;
const int MOD = 1000000007;

int main(){
    int D;
    cin >> D;

    vector<int> C(26);
    for (auto &i : C) cin >> i;

    vector<vector<int>> S(D, vector<int>(26));
    for (auto &i : S) for (auto &j : i) cin >> j;

    vector<int> last(26);

    rep(d, D) {
        int max_score = -INF, max_type = 0;
        rep(i, 26) {
            int res = S[d][i];
            int old_last = last[i];
            last[i] = d+1;
            rep(j, 26) res -= C[i] * ((d+1) - last[j]);
            if (chmax(max_score, res)) max_type = i;
            last[i] = old_last;
        }
        last[max_type] = d+1;
        cout << max_type+1 << endl;
    }
}

Measured memory_bytes: 3636
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	int x, y;
	cin >> x >> y;
	bool answer = false;
	for(int i = 0; i <= x; ++i){
		const int j = x - i;
		if(i * 2 + j * 4 == y){ answer = true; }
	}
	cout << (answer ? "Yes" : "No") << endl;
	return 0;
}



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

const int N = 1e5 + 3;
int n, k, s, ans[N];

int main() {
	scanf("%d %d %d", &n, &k, &s);
	for(int i = 1; i <= k; i++) ans[i] = s;
	for(int i = k + 1; i <= n; i++) ans[i] = s == 1e9 ? s - 1 : s + 1;
	for(int i = 1; i <= n; i++) printf("%d%c", ans[i], " \n"[i == n]);
	return 0;
}

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

using namespace std;

typedef long long ll;
typedef long double ld;

const int M = 107;

int n, m;
int l[M], r[M];
string s[M];

void read() {
  cin >> n >> m;
  for (int i = 0; i < n; ++i)
    cin >> s[i];
}

void no() {
  cout << "Impossible\n";
  exit(0);
}

void yes() {
  cout << "Possible\n";
  exit(0);
}


void kill() {
  for (int i = 0; i < n; ++i) {
    l[i] = 0;
    r[i] = m - 1;
    while (l[i] < m && s[i][l[i]] == '.')
      ++l[i];
    while (r[i] >= 0 && s[i][r[i]] == '.')
      --r[i];

    if (l[i] > r[i])
      no();

    for (int j = l[i]; j <= r[i]; ++j)
      if (s[i][j] != '#')
        no();
  }

  if (l[0] != 0)
    no();
  if (r[n - 1] != m - 1)
    no();

  for (int i = 0; i + 1 < n; ++i)
    if (r[i] != l[i + 1])
      no();

  yes();
}

int main() {
  cout.precision(20);
  cout << fixed;
  ios_base::sync_with_stdio(false);
  read();
  kill();
}


Measured memory_bytes: 384
#include "bits/stdc++.h"

int main() {
	int H, W;
	std::cin >> H >> W;
	std::vector<std::string> a;

	for (int i = 0; i < H; i++) {
		std::string str;
		std::cin >> str;
		if (str.find('#') == std::string::npos) continue;
		a.push_back(str);
	}

	std::vector<bool> ignore(W);
	for (int i = 0; i < W; i++) {
		bool ignore_check = true;
		for (auto b : a) {
			if (b[i] == '#') {
				ignore_check = false;
				break;
			}
		}
		if (ignore_check) {
			ignore[i] = true;
		}
	}

	// output
	for (auto b : a) {
		for (int i = 0; i < W; i++) {
			if (ignore[i] == false) {
				std::cout << b.at(i);
			}
		}
		std::cout << std::endl;
	}

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  double p;
  int n;
  while(cin>>p>>n,n){
    double t=sqrt(p);
    int x=0,y=1,u=1e9,v=1;
    for(int i=1;i<n;i++){
      int l=0,r=n+1,m;
      while(l<r){
    m=(l+r)/2;
    if(t<(1.0*m/i))r=m;
    else l=m+1;
      }
      if(x*i<(r-1)*y)x=r-1,y=i;
      if(r!=n+1&&u*i>v*r)u=r,v=i;
    }
    cout<<u<<'/'<<v<<' '<<x<<'/'<<y<<endl;
  }
  return 0;
}

Measured memory_bytes: 3156
def count_up(N, A, x, check, card, total):
  if check == N:
    return 1 if card > 0 and card * A == total else 0
  else:
    return count_up(N, A, x, check+1, card+1, total+x[check]) + count_up(N, A, x, check+1, card, total)

def bad_method(N, A, x):
  print count_up(N, A, x, 0, 0, 0)

def well_method(N, A, x):
  dp = [[[1 for a in range(N*50)] for b in range(N+1)] for c in range(N+1)]
  for j in range(N+1):
    for k in range(N+1):
      for s in range(N*50):
        if j == 0 and k == 0 and s == 0:
          dp[j][k][s] = 1
        elif j >= 1 and s < x[j-1]:
          dp[j][k][s] = dp[j-1][k][s]
        elif j >= 1 and k >= 1 and s >= x[j-1]:
          dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j-1]]
        else:
          dp[j][k][s] = 0

  answer = 0
  for i in range(1, N+1):
    answer += dp[N][i][A * i]
  print answer

def good_method(N, A, x):
  y = {}
  for i in range(len(x)):
    y[i] = x[i] - A
  dp = [[0 for a in range(N*50*2+1)] for b in range(N+1)]
  for j in range(N+1):
    for t in range(N*50*2+1):
      if j == 0 and t == N*50:
        dp[j][t] = 1
      elif j >= 1 and (t - y[j-1] < 0 or t - y[j-1] > N*50*2):
        dp[j][t] = dp[j-1][t]
      elif j >= 1 and 0 <= t - y[j-1] and t - y[j-1] <= N*50*2:
        dp[j][t] = dp[j-1][t] + dp[j-1][t-y[j-1]]
      else:
        dp[j][t] = 0

  print dp[N][N*50]-1

line = raw_input().split()
N = int(line[0])
A = int(line[1])
line = raw_input().split()
x = {}
for i in range(N):
  x[i] = int(line[i])

# bad_method(N, A, x)
# well_method(N, A, x)
good_method(N, A, x)

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

using namespace std;
using lli = int_fast64_t;
using ulli = uint_fast64_t;
#define debug(x) cerr << #x << " : " << x << endl
#define debugv(x) cerr << #x << " : {";for(auto value_of_x:x){ cerr << value_of_x << ", ";}cerr << endl
#define debugst(x) auto xt = x;cerr << #x << " : {";for(int i=0;i<x.size();i++){ cerr << xt.top() << ", ";xt.pop();}cerr << endl
#define debugvp(x) cerr << #x << " : {";for(auto value_of_x:x){ cerr << value_of_x.first << " : " << value_of_x.second << ", ";}cerr << endl

const lli MOD = 1000000007;
const lli LIMIT = 1000000000000000000 * 5;
const int tenfive = 100000;

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


Measured memory_bytes: 256
program main
implicit None
	integer(8)::n,k,i,p,q
	integer(8),allocatable::x(:)
	
	read *,n,k
	allocate(x(n))
	
	read *,x
	
	do i = 1,n-k+1
		if(abs(x(i)) < abs(x(i+k-1)))then
			q = abs(x(i))
			else
			q = abs(x(i+k-1))
		endif
		q = x(i+k-1)-x(i)+q
		if(i == 1 .or. p > q) p = q
	enddo
	
	print "(i0)",p
end program main

Measured memory_bytes: 1536
package main

import "fmt"

func main() {
	var N, A int
	fmt.Scan(&N, &A)
	x := make([]int, N)
	for i := 0; i < N; i++ {
		fmt.Scan(&x[i])
	}
	var dp [52][52][2560]int
	dp[0][0][0] = 1
	for i := 1; i <= N; i++ {
		for j := 0; j <= 50; j++ {
			for k := 0; k <= 2500; k++ {
				dp[i][j][k] += dp[i-1][j][k]
				dp[i][j+1][k+x[i-1]] += dp[i-1][j][k]
			}
		}
	}
	var ans int
	for j := 0; j <= 50; j++ {
		for k := 0; k <= 2500; k++ {
			if k == A*j {
				ans += dp[N][j][k]
			}
		}
	}
	fmt.Println(ans - 1)
	return
}


Measured memory_bytes: 54272
let pow x y z =
  let mult x1 y1 = ((x1 mod z)*(y1 mod z)) mod z in
  let rec f m n odd b = match n with
      0 -> 1
    | 1 -> mult m odd
    | _ -> let t = if n mod 2 = 1 then mult odd b else odd
           in f (mult m m) (n/2) t (mult b b)
  in f x y 1 x;;
 
let () =
  let f x y = pow x y 1000000007 |> Printf.printf "%d\n"
  in Scanf.scanf "%d %d\n" f;;

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

using namespace std;
using ll = long long;
int main() {
    int n; cin >> n;
    vector<ll> a(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }
    vector<ll> s(n+1, 0);
    for (int i = 0; i < n; ++i) {
        s[i+1] = s[i] + a[i];
    }

    map<ll, ll> mp;
    for (int i = 0; i < n+1; ++i) {
        ++mp[s[i]];
    }

    ll res = 0;
    for (auto it : mp) {
        ll num = it.second;
        res += num * (num - 1) / 2;
    }
    cout << res << endl;

    return 0;

}

Measured memory_bytes: 15872
import java.util.*;
public class Main {
    public static void main(String[] args) throws java.io.IOException{
        Scanner scan = new Scanner(System.in);

        while(true){
        	String tmp=scan.nextLine();
        	if(tmp.equals("END OF INPUT"))break;
        	String [] line =tmp.split(" ");
        	for(String s :line)
        		System.out.print(s.length());
        	if(scan.hasNext())System.out.println();
        	
        }
    }
}

Measured memory_bytes: 12000
#pragma GCC target ("avx2")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("O3")
#include"bits/stdc++.h"
#include<unordered_set>
#include<unordered_map>
#include<random>
using namespace std;
typedef long long ll;
const ll MOD = 1'000'000'007LL; /*998'244'353LL;*/
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(n); (i)++)

int X, Y;

signed main(){
    cin >> X >> Y;
    rep(i, X+1){
        int tmp = i*2 + (X-i)*4;
        if(tmp == Y){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
}

Measured memory_bytes: 3628
#include <stdio.h>
int main(void)
{

    
    int i,j,x,y;
    
    for(i=0; i<=x; i++){
        for(j=0; j<=y; j++){
            scanf("%d %d",&x,&y);
            if(x==0 && y==0)break;
    
        if(x<y)
            printf("%d %d\n",x,y);
        else
            printf("%d %d\n",y,x);
        }    
    }
    return 0;

}



Measured memory_bytes: 1980
/*---------------*/
/*   Darsein AC  */
/*  O(L n^2 2^n) */
/* imple: 18 min */
/* debug:  5 min */
/*---------------*/

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pii;

const int L = 0, R = 1, F = 2, B = 3, D = 4, U = 5;

void rotation(vi &dice, char dir){
  if(dir == 'L'){
    swap(dice[L],dice[U]); swap(dice[U],dice[R]); swap(dice[R],dice[D]);
  }
  if(dir == 'R'){
    swap(dice[R],dice[U]); swap(dice[U],dice[L]); swap(dice[L],dice[D]);
  }
  if(dir == 'F'){
    swap(dice[F],dice[U]); swap(dice[U],dice[B]); swap(dice[B],dice[D]);
  }
  if(dir == 'B'){
    swap(dice[B],dice[U]); swap(dice[U],dice[F]); swap(dice[F],dice[D]);
  }
}

int main(){
  map<char,int> dx,dy;
  dx['L'] = -1; dx['R'] = 1;
  dy['F'] = -1; dy['B'] = 1;

  int n;
  while(cin >> n){
    if(n==0)break;
    vector< map<pii,int> > paint(n);
    map<pii,int> mask;

    rep(i,n){
      pii pos;
      cin >> pos.first >> pos.second;
      vi dice(6);
      rep(j,6)cin >> dice[j];
      paint[i][pos] = dice[D];
      mask[pos] |= 1<<i;

      string rot;
      cin >> rot;
      rep(j,rot.size()){
	rotation(dice,rot[j]);
	pos.first += dx[rot[j]]; pos.second += dy[rot[j]];

	paint[i][pos] = dice[D];
	mask[pos] |= 1<<i;
      }
    }

    vi dp(1<<n,0);
    rep(bit,1<<n){
      rep(i,n){
	if( (bit>>i) & 1 )continue;

	int nxt = dp[bit];
	for(auto p : paint[i]){
	  pii pos = p.first;
	  int cost = p.second;

	  if(mask[pos]&bit)continue;
	  nxt += cost;
	}
	dp[bit|(1<<i)] = max(dp[bit|(1<<i)],nxt);
      }
    }

    cout << dp[(1<<n)-1] << endl;
  }
}

Measured memory_bytes: 3340
#include <bits/stdc++.h>
#include <stdlib.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
const ll BIG=1e15;

int main(){
    int N;cin>>N;
    vector<int> d(N+1);
    for(int i=1;i<=N;i++){
        int x; cin>>x;
        d.at(x)=i;
    }

    ll ans=0;
    multiset<int> S;
    S.insert(N+1);
    S.insert(N+1);
    S.insert(0);
    S.insert(0);
    for(ll i=N;i>=1;i--){
        S.insert(d.at(i));
        auto itr=S.find(d.at(i));
        ll  m0,l1,l2,r1,r2;
        itr++; r1=*itr;
        itr++; r2=*itr;
        itr--; itr--; m0=*itr;
        itr--; l2=*itr;
        itr--; l1=*itr;
        ans+=i*((r2-r1)*(m0-l2)+(r1-m0)*(l2-l1));
    }
    cout<<ans<<endl;


}

Measured memory_bytes: 5376
#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<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
#include<complex>
using namespace std;

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 998244353;
const ll INF = mod * mod;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef pair<ll, ll> LP;
typedef vector<ll> vec;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-5;
const ld pi = acos(-1.0);

bool used[2][2000][2001][2];
int memo[2][2000][2001][2];

int n;
vector<int> r, a, w,t;
int dfs(bool sta,int id, int rest,bool pre) {
	if (id == n)return 0;
	if (used[sta][id][rest][pre])return memo[sta][id][rest][pre];
	used[sta][id][rest][pre] = true;
	int ret = -mod;
	if (sta) {
		if (pre) {
			if (rest >= r[id]+1) {
				int nrest = rest - r[id];
				nrest = min(nrest, t[id]);
				ret = max(ret, dfs(true, id, nrest, true)+w[id]);
			}
		}
		else {
			if (rest >= r[id] + 1) {
				int nrest = rest - r[id];
				nrest = min(nrest, t[id]);
				ret = max(ret, dfs(true, id, nrest, true) + a[id]);
			}
		}
		ret = max(ret, dfs(true, id + 1, rest, false));
	}
	else {
		ret = max(ret, dfs(true, id, t[id], true)+a[id]);
		ret = max(ret, dfs(false, id + 1, 0, 0));
	}
	return memo[sta][id][rest][pre] = ret;
}

int dp[2001][2001];

bool comp(int a, int b) {
	return r[a] + t[a] > r[b] + t[b];
}
void solve() {
	cin >> n;
	vector<int> v;
	r.resize(n); a.resize(n); w.resize(n); t.resize(n);
	rep(i, n) {
		cin >> r[i] >> a[i] >> w[i] >> t[i];
		v.push_back(i);
	}
	sort(v.begin(), v.end(), comp);
	vector<int> cr = r, ca = a, cw = w, ct = t;
	rep(i, n) {
		r[i] = cr[v[i]];
		a[i] = ca[v[i]];
		w[i] = cw[v[i]];
		t[i] = ct[v[i]];
	}
	int ans = dfs(false, 0, 0, false);
	cout << ans << endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	//stop
	return 0;
}



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

namespace _178_b
{
    internal class ProductMax
    {
        private static void Main(string[] args)
        {
            var abcd = Console.ReadLine()?.Split(' ').Select(long.Parse).ToArray();
            if (abcd == null) return;
            var a = abcd[0];
            var b = abcd[1];
            var c = abcd[2];
            var d = abcd[3];

            var ac = a * c;
            var bd = b * d;
            var ad = a * d;
            var bc = b * c;
            var max1 = Math.Max(ac, bd);
            var max2 = Math.Max(ad, bc);
            var max = Math.Max(max1, max2);

            if (a <= 0 && b >= 0 || c <= 0 && d >= 0)
            {
                Console.WriteLine(Math.Max(max, 0));
                return;
            }

            Console.WriteLine(max);
        }
    }
}

Measured memory_bytes: 28004
#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_set>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
#include<bitset>
#include<complex>
#include<tuple>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef long double D;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;

//BEGIN CUT HERE
template<typename T,bool directed>
struct Dinic{
    struct edge {
        int to;
        T cap;
        int rev;
        edge(){}
        edge(int to,T cap,int rev):to(to),cap(cap),rev(rev){}
    };
    
    T INF;
    vector<vector<edge> > G;
    vector<int> level,iter;
    
    Dinic(){}
    Dinic(int n,T INF):INF(INF),G(n),level(n),iter(n){}
    
    void add_edge(int from,int to,int cap){
        G[from].emplace_back(to,cap,G[to].size());
        G[to].emplace_back(from,directed?0:cap,G[from].size()-1);
    }
    
    void bfs(int s){
        fill(level.begin(),level.end(),-1);
        queue<int> que;
        level[s]=0;
        que.emplace(s);
        while(!que.empty()){
            int v=que.front();que.pop();
            for(int i=0;i<(int)G[v].size();i++){
                edge &e=G[v][i];
                if(e.cap>0&&level[e.to]<0){
                    level[e.to]=level[v]+1;
                    que.emplace(e.to);
                }
            }
        }
    }
    
    T dfs(int v,int t,T f){
        if(v==t) return f;
        for(int &i=iter[v];i<(int)G[v].size();i++){
            edge &e=G[v][i];
            if(e.cap>0&&level[v]<level[e.to]){
                T d=dfs(e.to,t,min(f,e.cap));
                if(d==0) continue;
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
        return 0;
    }
    
    T flow(int s,int t,T lim){
        T fl=0;
        while(1){
            bfs(s);
            if(level[t]<0||lim==0) break;
            fill(iter.begin(),iter.end(),0);
            
            while(1){
                T f=dfs(s,t,lim);
                if(f==0) break;
                fl+=f;
                lim-=f;
            }
        }
        return fl;
    }
    
    T flow(int s,int t){
        return flow(s,t,INF);
    }
};
//END CUT HERE

const ll INF=100000;

int main(){
    ll h,w;
    cin>>h>>w;
    vector<string> A(h);
    for(auto &I:A){cin>>I;}
    Dinic<ll,false> F(h+w+2,INF);
    ll st=h+w;
    ll gl=st+1;
    for(int i=0;i<h;i++){
        for(int t=0;t<w;t++){
            if(A[i][t]=='o'){F.add_edge(i,h+t,1);}
            else if(A[i][t]=='S'){F.add_edge(st,i,INF); F.add_edge(st,h+t,INF);}
            else if(A[i][t]=='T'){F.add_edge(i,gl,INF); F.add_edge(h+t,gl,INF);}
        }
    }
    ll ans=F.flow(st,gl);
    if(ans>=INF){cout<<-1<<endl;}
    else{cout<<ans<<endl;}
    
    
    return 0;
}


Measured memory_bytes: 896
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <algorithm>

using namespace std;

int abc[100016][3];

int main() {
	int N;
	scanf("%d", &N);
	for(int i=0; i<N; ++i) {
		scanf("%d%d%d", &abc[i][0], &abc[i][1], &abc[i][2]);
	}
	int r[3] = {0};
	for(int i=0; i<N; ++i) {
		int a = max(r[1], r[2]) + abc[i][0];
		int b = max(r[2], r[0]) + abc[i][1];
		int c = max(r[0], r[1]) + abc[i][2];
		r[0] = a;
		r[1] = b;
		r[2] = c;
	}
	printf("%d\n", max(max(r[0], r[1]), r[2]));
	return 0;
}


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

int main(){
  int n;
  int b, f, r, v;
  int a[4][3][10]={};

  cin >> n;
  for(int i=0; i<n; i++){
      cin >> b >> f >> r >> v;
      a[b-1][f-1][r-1]+=v;
  }

  for(int i=0; i<4; i++){
    for(int j=0; j<3; j++){
      for(int k=0; k<10; k++){
        cout << " " << a[i][j][k];
      }
      cout << endl;
    }
    if(i!=3)cout << "####################" << endl;
  }
}



Measured memory_bytes: 3116
#include<bits/stdc++.h>
#define N 1000
using namespace std;
typedef long long LL;
class memo
{
private:
    int A,B,C,D,E,F;
    bool table[3005];
    int frontmin[3005];
    int tablew[3005];
    int frontwmin[3005];

public:
    void in()
    {
        cin>>A>>B>>C>>D>>E>>F;
    }
    pair<int,int> slove();
    memo();
};
memo::memo()
{
    memset(table,0,sizeof(table));
    memset(frontmin,0,sizeof(frontmin));
    memset(tablew,0,sizeof(tablew));
    memset(frontwmin,0,sizeof(frontwmin));
}
pair<int,int> memo::slove()
{
    int a,b;
    a = A*100,b = B*100;
    double maxx = 0;
    int ia = 0,ib,ic = 0;
    for(int i = 0; i <= F/C; i++)
    {
        for(int j = 0; j <= F/D; j++)
        {
            if(i*C + j*D <= F)
                table[i*C + j*D] = true;
        }
    }
    for(int i = 0; i <= F; i++)
    {
        if(table[i])
            frontmin[i] = i;
        else  frontmin[i] = frontmin[i-1];
    }
    for(int i = 0; i <= F/a; i++)
    {
        for(int j = 0; j <= F/b; j++)
        {
            if(i*a + j*b <= F)
                tablew[i*a+j*b] = true;
        }
    }
    for(int i = 1; i <= F; i++)
    {
        if(tablew[i])
        {
            int sum = F - i;
            int sumr = i/100*E;
            sumr = min(sum,sumr);
            sumr = frontmin[sumr];
            if((maxx <= 1.0*sumr/(i+sumr))&&i+sumr!=0)
                maxx = 1.0*sumr/(i+sumr),ia = sumr + i,ic = sumr;
        }
    }
    return make_pair(ia,ic);
}
int main(void)
{
    memo ask;
    ask.in();
    pair<int,int>ac = ask.slove();
    printf("%d %d\n",ac.first,ac.second);
    return 0;
}


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

using namespace std;

int n, cnt[100][26];

int main() {
  cin >> n;
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    for (int l = 0; l < (int) s.size(); l++) {
      int tmp = s[l] - 'a';
      cnt[i][tmp]++;
    }
  }
  string ans = "";
  for (int i = 0; i < 26; i++) {
    int sml = 1e9;
    for (int j = 0; j < n; j++) {
      sml = min(sml, cnt[j][i]);
    }
    for (int l = 0; l < sml; l++) {
      ans += (char) ('a' + i);
    }
    //cout << (char) ('a' + i) << ' ' << sml << endl;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::{Write, BufWriter};
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};
    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, [graph1; $len:expr]) => {{
        let mut g = vec![vec![]; $len];
        let ab = read_value!($next, [(usize1, usize1)]);
        for (a, b) in ab {
            g[a].push(b);
            g[b].push(a);
        }
        g
    }};
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };
    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };
    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };
    ($next:expr, usize1) => (read_value!($next, usize) - 1);
    ($next:expr, [ $t:tt ]) => {{
        let len = read_value!($next, usize);
        read_value!($next, [$t; len])
    }};
    ($next:expr, $t:ty) => ($next().parse::<$t>().expect("Parse error"));
}

#[allow(unused)]
macro_rules! debug {
    ($($format:tt)*) => (write!(std::io::stderr(), $($format)*).unwrap());
}
#[allow(unused)]
macro_rules! debugln {
    ($($format:tt)*) => (writeln!(std::io::stderr(), $($format)*).unwrap());
}

/// Ported from ACL.
/// Computes \sum_{i = 0}^{n - 1} floor((a * i + b) / m).
fn floor_sum(n: i64, m: i64, mut a: i64, mut b: i64, mut acc: i64) -> i64 {
    if a >= m {
        let q = a / m;
        acc += (n - 1) * n / 2 * q;
        a -= q * m;
    }
    if b >= m {
        let q = b / m;
        acc += n * q;
        b -= q * m;
    }
    let y_max = (a * n + b) / m;
    let x_max = y_max * m - b;
    if y_max == 0 {
        return acc;
    }
    acc += (n - (x_max + a - 1) / a) * y_max;
    let mut sub_b = a - x_max % a;
    if sub_b >= a {
        sub_b -= a;
    }
    floor_sum(y_max, a, m, sub_b, acc)
}

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (let _ = write!(out,$($format)*););
    }
    input! {
        nmab: [(i64, i64, i64, i64)],
    }
    for (n, m, a, b) in nmab {
        puts!("{}\n", floor_sum(n, m, a, b, 0));
    }
}

fn main() {
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 104_857_600; // 100 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}


Measured memory_bytes: 3812
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
///                    BISMILLAHIR RAHMANIR RAHIM

int main()
{
  ll x;
    cin >> x;
    ll t = 100;
    ll ans = 0;
    while (t < x) {
        t += t / 100;
        ans++;
    }
    cout << ans;
    return 0;
}

/// A L H A M D U L I L L A H


Measured memory_bytes: 3608
#include<stdio.h>
int main()
{
	int a,b;
	scanf("%c ",&a);
	scanf("%c",&b);
	a=a-55;
	b=b-55;
	if(a>b)
	{
		printf(">");
	}
	else if(a<b)
	{
		printf("<");
	}
	else
	{
		printf("=");
	}
	return 0;
}

Measured memory_bytes: 128
#! /usr/bin/env python3

import copy
import sys

def solve(n, actions, offset):

    res = 0
    val = 1000000
    if n == 0 or len(actions) == 0:
        return(offset)
    while (val > n):
        val = actions.pop()
    if val == 1:
        return(n + offset)
    while n >= val * 3:
        res += 1
        n -= val
    tmp = 1000000
    i = 0
    while n >= 0:
        tmp = min(tmp, solve(copy.copy(n), copy.copy(actions), copy.copy(i)))
        i += 1
        n -= val
    return(tmp + res + offset)


n = int(input())

res = 0

actions = [1]

for i in range(1, 6 + 1):
    actions.append(6 ** i)
    actions.append(9 ** i)

print(solve(n, actions, 0))


Measured memory_bytes: 3444