akhauriyash/Code-Regression huggingface dataset:
import copy
import sys
from collections import deque
H,W = (int(_) for _ in input().split())  
f_tmp = []
for _ in range(H):
    f_tmp.append(list(input()))
dp = [[0] * (W+1) for i in range(H+1)]
#dにスタート位置を入力する
d = [[1, 0], [-1, 0], [0, 1], [0, -1]]
max_root = 0
for s_i in range(H):
    for s_j in range(W):
        f = copy.deepcopy(f_tmp)
        if f[s_i][s_j] != '#':
            q = deque()
            q.append([s_i,s_j,0])
            flg = False
            while len(q)>0:
                #print(f)
                #print(q)
                node = q.popleft()
                if node is not None:
                    y = node[0]
                    x = node[1]
                    z = node[2]
                    f[y][x] = '#'
                    for dx, dy in d:
                        nx, ny = x + dx, y + dy
                        if not (0 <= nx < W and 0 <= ny < H) or f[ny][nx] == '#':
                            #print("NG")
                            continue
                        else:
                            tmp = [ny,nx,z+1]
                            if f[ny][nx] != 'y':
                                q.append(tmp)
                            if f[ny][nx] == 'g' and flg == False:
                                flg = True
                                if max_root < z+1:
                                    max_root = z+1
                            f[ny][nx] = 'y'
                            
                            if max_root < z+1:
                                max_root =z+1
print(max_root)

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

using namespace std;

#define rep(i , j , k) for (int i = j; i < k; i++)
#define pb push_back
#define for_all(x) x.begin(),x.end()

typedef long long ll;
typedef pair<int , int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef long double ld;

inline void fileIO(string s) {
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}

template<class T , class S>
inline void smin(T &a, S b) {
	if (a > b)
		a = b;
}

template<class T , class S>
inline void smax(T &a, S b) {
	if (a < b)
		a = b;
}

constexpr int N = 4e5 + 10;

int H , W , n;
int r , c;
string S , T;

pii q[N];
int  R;

inline void input() {
	cin >> H >> W >> n >> r >> c >> S >> T;
}

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

	input();

	rep(i , 0 ,n) {
		if (S[i] == 'L' || S[i] == 'R')
			q[R++] = {S[i] , 0};
		if (T[i] == 'L' || T[i] == 'R')
			q[R++] = {T[i] , 1};
	}

	int left = 0, right = W + 1;
	while (R--) {
		if (q[R].second) {
			if (q[R].first == 'L')
				right++;
			else
				left--;
		}	
		else {
			if (q[R].first == 'L')
				left++;
			else
				right--;

		}
		smax(left , 0);
		smin(right , W + 1);

		if (left == right - 1)
			return cout << "NO\n", 0;

	}
	
	R++;

	if (c <= left || c >= right)
		return cout << "NO\n", 0;



	rep(i , 0 ,n) {
		if (S[i] == 'U' || S[i] == 'D')
			q[R++] = {S[i] , 0};
		if (T[i] == 'D' || T[i] == 'U')
			q[R++] = {T[i] , 1};
	}

	left = 0, right = H + 1;
	while (R--) {
		if (q[R].second) {
			if (q[R].first == 'U')
				right++;
			else
				left--;
		}	
		else {
			if (q[R].first == 'U')
				left++;
			else
				right--;

		}
		smax(left , 0);
		smin(right , H + 1);

		if (left == right - 1)
			return cout << "NO\n", 0;

	}

	if (r <= left || r >= right)
		return cout << "NO\n", 0;
	
	cout << "YES\n";

	return 0;
}


Measured memory_bytes: 2456
#include <iostream>
#include <vector>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

int main()
{
  int n, m, k;
  cin >> n >> m >> k;
  
  vector<int> a(n);
  vector<int> b(m);
  
  rep(i, n){
    cin >> a.at(i);
  }
  
  rep(i, m){
    cin >> b.at(i);
  }
  
  long long t = 0;
  
   
  rep(i, m){
    t += b.at(i);
  }
  
  int answer = 0;
  int j = m; 
  
  rep(i, n + 1){
    while(j > 0 && t > k){
      j--;
      t -= b.at(j);
    }
    
    if(t > k)
      break;
    
    answer = max(answer, i + j);
      
    if(i == n)
      break;
    
    t += a.at(i);
  }
  
  cout << answer << endl;
}


Measured memory_bytes: 4844
#include<bits/stdc++.h>
using namespace std;
 
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define f0(i,a,b) for(int i=a;i<b;i++)
#define f1(i,a,b) for(int i=a;i<=b;i++)
#define f2(i,a,b) for(int i=a;i>b;i--)
#define f3(i,a,b) for(int i=a;i>=b;i--)
#define all(a) a.begin(),a.end()
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define int long long
#define fi first
#define se second
#define mod 1000000007
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define test int t;cin>>t;while(t--)

signed main(){
    fast
string s="No";
 int n;
 cin>>n;int c=0;int r=0;
 f0(i,1,n+1)
 {int y=(n-1)/i;
 c+=y;
 if(y>=i)r++;;
 }cout<<c<<endl;
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define rep(I, N) for (int I = 1; I <= (N); ++I)
#define repp(I, N) for (int I = 0; I < (N); ++I)
#define FOR(I, A, B) for (int I = (A); I <= (B); ++I)
#define FORR(I, A, B) for (int I = (A); I >= (B); I--)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
using namespace std;
const int N = 2e5 + 5;
const double eps = 1e-7;
const int mod = 1e9 + 7;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<PII> VPII;
typedef pair<LL,LL> PLL;
typedef vector<PLL> VPLL;
LL gcd(LL a,LL b){return b>0?gcd(b,a%b):a;}
LL ksm(LL a,LL b){LL ans = 1;while(b){if(b&1) ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans % mod;}
int a[N];
vector<int> v;

int b[N];
int main() {
    int n;
    cin >> n;
    //memset(b, -1, sizeof - 1);
    for (int i = 1; i <= n;i++) cin >> a[i];
    for (int i = n; i >= 1;i--)
    {
        int cnt = 0;
        for (int j = i; j <= n;j += i)
        {
            cnt ^= b[j];
        }
        if(a[i] != cnt)
        {
            b[i] = 1;
            v.push_back(i);
        }
    }
    if(SZ(v)) 
    {
        cout << SZ(v) << endl;
        for (int i = 0; i < SZ(v);i++)
            cout << v[i] << ' ';
    }
    else 
    {
        cout << 0 << endl;
    }
    return 0;
}


Measured memory_bytes: 2936
import java.util.Scanner;
public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int x = sc.nextInt();
    int t = sc.nextInt();
    if((x-t)<=0){
      System.out.println(0);
    }else{
      System.out.println(x-t);
    }
  }
}

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

using namespace std;


int main() {
	string S;
	cin >> S;
	for( size_t i = 0; i < S.size() - 1; i++ ) {
		if( S[i] == S[i + 1] ) {
			cout << i + 1 << " " << i + 2 << endl;
			return 0;
		}
	}
	for( size_t i = 0; i < S.size() - 2; i++ ) {
		if( S[i] == S[i + 2] ) {
			cout << i + 1 << " " << i + 3 << endl;
			return 0;
		}
	}
	cout << -1 << " " << -1 << endl;
}

Measured memory_bytes: 512
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <bitset>

using namespace std;
typedef long long ll;

int main() {
	int N, Q; cin >> N >> Q;
	int* ans = new int[Q];
	for (int i = 0; i < Q; i++) {
		ans[i] = -1;
	}
	multimap<int, pair<int, int>> mp;
	for (int i = 0; i < N; i++) {
		int s, t, x; cin >> s >> t >> x;
		mp.insert({ x, {s - x, t - x} });
	}
	map<int, int> table;
	set<int> st;
	for (int i = 0; i < Q; i++) {
		int x; cin >> x;
		st.insert(x);
		table.insert({ x, i });
	}
	for (auto itr = mp.begin(); itr != mp.end(); itr++) {
		int s = itr->second.first;
		int t = itr->second.second;
		auto sitr = st.lower_bound(s);
		while (sitr != st.end() && *sitr < t) {
			int x = *sitr;
			ans[table[x]] = itr->first;
			sitr = st.erase(sitr);
		}
	}

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

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

int main() {
  int N;
  int K;
  vector <int> gyumolcs;
  cin >> N;
  cin >> K;
  int seged;
  for(int i=0;i<N;i++){
    cin >> seged;
    gyumolcs.push_back(seged);
  }
  int oszzeadas=0;
  for(int j=0;j<K;j++){
    int min=gyumolcs[0];
    int mini=0;
    for(int i=1;i<gyumolcs.size();i++){
      if(gyumolcs[i]<min){
        min=gyumolcs[i];
        mini=i;
      }
      }
      oszzeadas+=min;
      gyumolcs[mini]+=1000;
    
  }
  cout << oszzeadas;
	return 0;
}


Measured memory_bytes: 3636
#include <iostream>
#include <fstream>
#include <string>
#include <stdio.h>
#include <string.h>

using namespace std;

const int MAX = 100000;

typedef struct {
    int time;
    char name[11];
} process_mine_t;

void pp_process(process_mine_t *p){
    cout << "process:" << p->name << " " << p->time << endl;
}

typedef struct {
    process_mine_t *p[MAX];
    int head,tail;
} queue_mine_t;

void pp_queue(queue_mine_t *q, int i){
    cout << "queue[" << i << "]:" ;
    pp_process(q->p[i]);
}

void pp_queue_pointer(queue_mine_t *q){
    cout << "queue:head " << q->head << " queue:tail " << q->tail << endl;
}

void initialize(queue_mine_t *t){
    t->tail = t->head = 0;
}

int isEmpty(queue_mine_t *t){
    return t->tail == t->head;
}

int isFull(queue_mine_t *t){
    return t->head == (t->tail +1)%MAX;
}

int enqueue_mine(queue_mine_t *t, process_mine_t *p){
    if (isFull(t)){ return 0; }
    else{
        t->p[t->tail] = p;
        if (t->tail +1 == MAX){
            t->tail =0;
        }else{t->tail += 1;}
        return 1;
    }
}

int dequeue_mine(queue_mine_t *t, process_mine_t **p){
    if(isEmpty(t)){ return 0;}
    else{
        *p = (t->p[t->head]);
        if(t->head + 1 == MAX){
            t->head = 0;
        }else{
            t->head++;
        }
        return 1;
    }

}



int main(){

    queue_mine_t que;
    queue_mine_t *p = &que;
    initialize(p);
    process_mine_t process[MAX]={};
    process_mine_t *process_mine=process;
    int flag=1;
    int n,q,alltime=0;
    char c[11];
    int time_temp;
    cin  >> n >> q;
    for(int i=0;i<n && flag;i++){
        cin >> c >> time_temp;
        process_mine = process + i;
        strcpy(process_mine->name,c);
        process_mine->time = time_temp;
        flag = enqueue_mine(p,process_mine);
    }

    while(flag){
        flag = dequeue_mine(p,&process_mine);
        if(!flag){break;}
        if(q >= process_mine->time){
            cout << process_mine->name << " " << (alltime += process_mine->time)<<endl;
        }else{
            process_mine->time -= q;
            flag = enqueue_mine(p, process_mine);
            alltime += q;
         }
    }
    return 0;
}



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

int main(){
    int k;
    int a,b;
    scanf("%d%d%d",&k,&a,&b);
    if(a%k == 0){
        printf("OK\n");
    }else if(a/k * k +k <= b){
        printf("OK\n");
    }else{
        printf("NG\n");
    }
}

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

int main() {
    string s; cin >> s;
    int n = s.size();
    rep(i,n) cout << 'x';
    cout << endl;
}


Measured memory_bytes: 256
checkChar :: Char -> Char
checkChar n
  | ('a' <= n && n <= 'z') = 'a'
  | ('A' <= n && n <= 'Z') = 'A'

fac :: Int -> Int
fac n
  | n <= 1 = 1
  | n > 1 = n*(fac (n-1))

main = do
    x <- getChar
    putChar (checkChar x)
    putChar '\n'


Measured memory_bytes: 3732
#include<stdio.h>
#include<stdlib.h>
#define INF 1000000001
typedef struct vertice
{
  int cost;
  int status;
  int numOfAdj;
  int *adjList;
  int *costList;
} ver;
ver *v;
int n;//the number of vertices
void init();
void setArray(int);
void dijkstra(void);
int main(void)
{
  int i,j;//counter
  int key;
  scanf("%d",&n);
  init();
  for(i=0;i<n;i++)
    {
      scanf("%d",&key);
      scanf("%d",&v[key].numOfAdj);
      setArray(key);
      for(j=0;j<v[key].numOfAdj;j++) scanf("%d%d",&v[key].adjList[j],&v[key].costList[j]);
    }
  dijkstra();
  free(v);
  return 0;
}
void init(void)
{
  int i;//counter
  v=(ver*)malloc(sizeof(ver)*n);
  for(i=0;i<n;i++)
    {
      v[i].numOfAdj=0;
      v[i].status=0;
      v[i].cost=INF;
    }
}
void setArray(int key)
{
  v[key].adjList=(int*)malloc(sizeof(int)*v[key].numOfAdj);
  v[key].costList=(int*)malloc(sizeof(int)*v[key].numOfAdj);
}
void dijkstra(void)
{
  int i;//count
  int current=0;
  int viewing;
  int next;
  int minCost;
  v[0].cost=0;
  for(;;)
    {
      v[current].status=1;
      minCost=INF;
      for(i=0;i<v[current].numOfAdj;i++)
        {
          viewing=v[current].adjList[i];
          if(v[viewing].status==0)
            {
              if(v[current].cost+v[current].costList[i]<v[viewing].cost)
                {
                  v[viewing].cost=v[current].cost+v[current].costList[i];
                  //printf("v[%d].cost=%d\n",viewing,v[viewing].cost);
                }
            }
        }
      for(viewing=0;viewing<n;viewing++)
        {
          if(v[viewing].status==0&&v[viewing].cost<minCost)
            {
              minCost=v[viewing].cost;
              next=viewing;
            }
        }
      if(minCost==INF) break;
      //printf("next->%d\n",next);
      current=next;
    }
  for(i=0;i<n;i++) printf("%d %d\n",i,v[i].cost);
}


Measured memory_bytes: 5656
h, w = map(int, input().split())
l = []
r = []

for i in range(h):
    ls = list(input())
    if "#" in ls:
        l.append(ls)
        for j in range(w):
            if ls[j] == "." and j not in r:
                r.append(j)

s = [i for i in range(w)]

for i in r:
  count = 0
  for j in range(len(l)):
    if l[j][i] == ".":
      count += 1
  if count == len(l):
    s.remove(i) 

ans = []
for i in range(len(l)):
  a = []
  for j in s:
    a.append(l[i][j])
  ans.append(a)
  

for i in range(len(l)):
  b = "".join(ans[i])
  print(b)
  



Measured memory_bytes: 9160
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <numeric>
#include <iterator>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int,int> PII;
typedef vector<PII> VPII;
typedef istringstream ISS;
typedef ostringstream OSS;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )
#define EACH( it, c ) for ( auto it = c.begin(); it != c.end(); ++it )
#define ALL( c ) (c).begin(), (c).end()
#define DRANGE( c, p ) (c).begin(), (c).begin() + p, (c).end()

#define PB( n ) push_back( n )
#define MP( a, b ) make_pair( ( a ), ( b ) )
#define EXIST( c, e ) ( (c).find( e ) != (c).end() )

#define fst first
#define snd second

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

#include <complex>
typedef complex<double> Point;
const double EPS = 1e-8;

// テ・ツ?・テ・ツ環崚」ツつケテ」ツδ暗」ツδェテ」ツδシテ」ツδ?」ツ?凝」ツつ嘉・ツョツ淌ヲツ閉ーテ、ツコツ古」ツ?、テ」ツつ津」ツ?ィテ」ツ?」テ」ツ?ヲ Point テ」ツ?ク
istream& operator >> ( istream &s, Point &a )
{
	double r, i;
	s >> r >> i;
	a = Point( r, i );
	return s;
}

// テ・ツ、ツ姪ァツゥツ催ッツシツ暗」ツつッテ」ツδュテ」ツつケテァツゥツ催ッツシツ?
double cross( const Point &a, const Point &b )
{
	return a.real() * b.imag() - a.imag() * b.real();
}

// CCW テゥツ鳴「テヲツ閉ーテ」ツ?? -> b -> c テ」ツ?ィテゥツ?イテ」ツつ?」ツ?ィテ」ツ?催」ツ??・ツ渉催ヲツ卍づィツィツ暗・ツ崢榲」ツつ甘」ツ?ェテ」ツつ?-1, テァツ崢エテゥツ?イテ」ツ?ェテ」ツつ?0, テヲツ卍づィツィツ暗・ツ崢榲」ツつ甘」ツ?ェテ」ツつ?1
int ccw( const Point &a, const Point &b, const Point &c )
{
	if ( cross( ( b - a ), ( c - a ) ) < -EPS )
	{
		return -1;
	}
	else if ( EPS < cross( ( b - a ), ( c - a ) ) )
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

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

	for ( Point a, b, c, p; cin >> a >> b >> c >> p; )
	{
		vector<Point> ps( 4 );
		ps[0] = a;
		ps[1] = b;
		ps[2] = c;
		ps[3] = a;

		int sum = 0;
		REP( i, 0, 3 )
		{
			sum += ccw( ps[i], ps[ i + 1 ], p );
		}
		cout << ( abs( sum ) == 3 ? "YES" : "NO" ) << endl;
	}

	return 0;
}

Measured memory_bytes: 1220
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define INF (1e9)
#define PI (acos(-1))
#define print(x) cout << x << endl
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl

int main() {
    int A, B;  cin >> A >> B;
    string S;  cin >> S;

    string a;
    string b;
    char h;
    a = S.substr(0, A);
    b = S.substr(A+1, B);
    h = S[A];

    bool flag = true;
    rep(i, A) {
        if (a[i] == '-') flag = false;
    }
    rep(i, B) {
        if (b[i] == '-') flag = false;
    }
    if (h != '-') flag = false;

    if (flag)  yes;
    else no;

}




Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        double[] a = new double[n];
        double res = 1;
        double tmp = 0;

        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextDouble();
            res *= a[i];
        }
        for (int i = 0; i < n; i++) {
            tmp += res / a[i];
        }

        System.out.println(res / tmp);
    }
}



Measured memory_bytes: 24532
#include<iostream>
using namespace std;
int main(){
  while(1){
    int n,m;
    cin>>n>>m;
    if(n==0 && m==0)
      break;
    int a[1000];
    for(int i=0;i<n;i++){
      cin>>a[i];
    }
    int sum = -1;
    for(int i=0;i<n-1;i++){
      for(int j=i+1;j<n;j++){
        int p=a[i]+a[j];
        if(p<=m && p>sum)
          sum=p;
      }
    }
    if(sum!=-1){
      cout<<sum<<endl;
    }else{
      cout<<"NONE"<<endl;
    }
  }
  return 0;
}



Measured memory_bytes: 3100
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i,N) for(int i = 0; i < (N); i++)
#define erep(i,N) for(int i = N - 1; i >= 0; i--)
const ll INF = 1000000000;
//const ll MOD = 1000000007;
const ld PI = (acos(-1));
using Graph = vector<vector<int>>;
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;}
typedef pair<int, int> P;
typedef pair<ll,ll> PLL;
double rad(double a) {return a * 180 / PI;}

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号 (例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

//dpTable
int dp[100050];

int main(){
    double D,T,S;
    cin >> D >> T >> S;
    cout << (D / T <= S ? "Yes" : "No") << endl;
    return 0;
}


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

using namespace std;

typedef long long ll;
typedef pair<int,int> P;
const double EPS = 1e-12;
const int INF = numeric_limits<int>::max()/2;
const int MOD = 1e9+7;

struct RMQ {
	using type = ll;
	static type id() { return 0; }
	static type op(const type& l, const type & r) { return max(l, r); }
};

struct RSQ {
	using type = int;
	static type id() { return 0; }
	static type op(const type& l, const type & r) { return l + r; }
};

struct RMSQ {
	struct type {
		ll left, right, all, sum;
		type() : left(-INF), right(-INF), all(-INF), sum(0) {}
		type(ll val) : left(val), right(val), all(val), sum(val) {}
		type(ll l, ll r, ll a, ll s) : left(l), right(r), all(a), sum(s) {}
	};
	static type id() { return type(); }
	static type op(const type& l, const type & r) {
		return type(max(l.left, l.sum + r.left), max(r.right, r.sum + l.right), max({ l.all, r.all, l.right + r.left }), l.sum + r.sum);
	}
};

// segment tree
template <typename M>
class segment_tree {
	using T = typename M::type;
	const int n;
	vector<T> data;
	int size(int n) {
		int res;
		for (res = 1; res < n; res <<= 1);
		return res;
	}
public:
	segment_tree(int n_) : n(size(n_)), data(n * 2, M::id()) {}
	segment_tree(int n_, T val) : n(size(n_)), data(n * 2, val) {}
	void init(const vector<T>& data_) {
		for (int i = 0; i < (int)data_.size(); i++)
			data[i + n] = data_[i];
		for (int i = n - 1; i >= 0; i--)
			data[i] = M::op(data[i * 2], data[i * 2 + 1]);
	}
	void update(int p, T val) {
		p += n;
		data[p] = val;
		while (p >>= 1) data[p] = M::op(data[p * 2], data[p * 2 + 1]);
	}
	void add(int p, T val) {
		p += n;
		data[p] += val;
		while (p >>= 1) data[p] = M::op(data[p * 2], data[p * 2 + 1]);
	}
	T find(int l, int r) {
		l += n; r += n + 1;
		T res1 = M::id(), res2 = M::id();
		while (l < r) {
			if (l & 1) res1 = M::op(res1, data[l++]);
			if (r & 1) res2 = M::op(data[--r], res2);
			l >>= 1; r >>= 1;
		}
		return M::op(res1, res2);
	}
};

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

    int n;cin>>n;
    vector<int> x(n);
    for(int i=0;i<n;i++) cin>>x[i];
    segment_tree<RMQ> st(111111);
    vector<ll> dp(111111,0);
    ll res=0,sum=0;
    for(int i=0;i<n;i++){
        dp[i] = st.find(0,x[i]-1) + x[i];
        st.update(x[i],dp[i]);
        res=max(res,dp[i]);
        sum += x[i];
    }
    cout<<sum-res<<endl;

}


Measured memory_bytes: 6264
#[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, ( $($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);
        (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    }};

    ($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());
}

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (let _ = write!(out,$($format)*););
    }
    input! {
        n: usize, m: usize,
    }
    // not (2|n) -> -1 0, -2 1, -3 2, ...
    // 2|n -> -1 0, -2 1, ..., n/2-1 n/2+1,n/2-2 n/2+2
    let mut ans = vec![];
    if n % 2 == 1 {
        for i in 0..m {
            ans.push((n - i - 1, i));
        }
    } else {
        for i in 0..m {
            let j = i / 2;
            if i % 2 == 0 {
                ans.push((n - j - 1, j));
            } else {
                ans.push((n / 2 + j + 1, n / 2 - j - 1));
            }
        }
    }
    assert_eq!(ans.len(), m);
    for &(a, b) in &ans {
        puts!("{} {}\n", a + 1, b + 1);
    }
}

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: 3008
//http://arc078.contest.atcoder.jp/tasks/arc078_b
#include <bits/stdc++.h>

using namespace std;
int win = 0;//1:fennec, 2: snuke.
const int MAXN = 120000;
int dist[2][MAXN];
void dfs(int node,int prev,int c,int vis[],vector<vector<int> >& g)
{
    vis[node]=1;
    dist[c][node] = prev+1;
    for(int i=0;i<g[node].size();i++)
    {
        int n = g[node][i];
        if(!vis[n])
        {
            dfs(n,dist[c][node],c,vis,g);
        }
    }
}

int main()
{
    int n;
    cin>>n;
    vector<vector<int> > g(n+1);
    for(int i=0;i<n-1;i++)
    {
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int vis[n+1]={};
    dfs(1,-1,0,vis,g);
    memset(vis,0,sizeof(vis));
    dfs(n,-1,1,vis,g);
    int sb = 0,sw = 0;
    for(int i=1;i<=n;i++)
    {
        //printf("i: %d,from 1: %d, from n: %d\n",i,dist[0][i],dist[1][i]);
        if(dist[0][i] <= dist[1][i]) ++sb;
        else ++sw;
    }
    if(sb>sw) cout<<"Fennec\n";
    else
    {
        cout<<"Snuke\n";
    }
    return 0;
}


Measured memory_bytes: 13184
//*******Abhijit Burman***********// 
//Jalpaiguri Government Engineering College/ 

#include<bits/stdc++.h> 
using namespace std; 
#define ll long long int 
#define pb push_back 
#define mk make_pair 
#define MAXX (1000000000000000000+7) 
#define fio ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL) 



int solve()
{
    ll n;
    cin>>n;
    
    ll temp = n/500;
    
    n=n-temp*500;
    
    ll temp1 = n/5;
    
    cout<<temp1*5+temp*1000<<endl;
    
    
    
    return 0;
}
    

int main()
{
    fio;
    ll tt=1;
    // cin>>tt;
    while(tt--)
    {
        solve();
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
 int n,Max=1;
 cin>>n;
 map<int,int>m;
 for(int i = 0 ; i < n ; i++){
    int num;
    cin>>num;
    m[num]++;
    m[num-1]++;
    m[num+1]++;
 }
 for(pair<int,int> c:m){
    if(c.second>Max) Max=c.second;
 }
 cout<<Max;
    return 0;
}


Measured memory_bytes: 4736
/**
 *    author:  tourist
 *    created: 13.10.2018 15:21:35       
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n), b(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i] >> b[i];
  }
  long long sa = 0, sb = 0;
  vector<pair<int,int>> x;
  for (int i = 0; i < n; i++) {
    x.emplace_back(a[i], i);
    x.emplace_back(b[i], i);
    sa += a[i];
    sb += b[i];
  }
  sort(x.begin(), x.end());
  vector<long long> pref(x.size() + 1);
  pref[0] = 0;
  for (int i = 0; i < (int) x.size(); i++) {
    pref[i + 1] = pref[i] + x[i].first;
  }
  vector<vector<int>> pos(n);
  for (int i = 0; i < (int) x.size(); i++) {
    pos[x[i].second].push_back(i);
  }
  long long sum = (long long) 2e18;
  for (int i = 0; i < n; i++) {
    int j = n;
    while (true) {
      int cc = (pos[i][0] < j) + (pos[i][1] < j);
      if (cc == j - n) {
        break;
      }
      j++;
    }
    long long cur = pref[j];
    if (pos[i][0] < j) {
      cur -= x[pos[i][0]].first;
    }
    if (pos[i][1] < j) {
      cur -= x[pos[i][1]].first;
    }
    sum = min(sum, cur);
  }
  sum = min(sum, min(sa, sb));
  cout << sum << '\n';
  return 0;
}


Measured memory_bytes: 9584
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
using namespace std;
#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
typedef long long ll;
#define INF (1<<29)

int main(){
  string s;
  long long int k, x;
  cin >> s >> k;
  for(int i=0;i<s.length();i++){
    x++;
    if(s[i]!='1')
      break;
  }
  if(x>k)cout << '1' << endl;
  else cout << s[x-1] << endl;
  return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int q = Integer.parseInt(br.readLine());
		PriorityQueue<Int2> pq1 = new PriorityQueue<Int2>();
		PriorityQueue<Integer> pq2 = new PriorityQueue<Integer>();
		int x = 0;
		long v = 0;
		for (int i = 0; i < q; i++) {
			String[] sa = br.readLine().split(" ");
			int y = Integer.parseInt(sa[0]);
			if (y == 1) {
				int a = Integer.parseInt(sa[1]);
				int b = Integer.parseInt(sa[2]);
				Int2 o = new Int2();
				o.i = a;
				pq1.add(o);
				pq2.add(a);
				if (pq1.peek().i != pq2.peek()) {
					Int2 r = pq1.poll();
					int s = pq2.poll();
					v += Math.abs(r.i - s);
					int t = s;
					s = r.i;
					r.i = t;
					pq1.add(r);
					pq2.add(s);
				}
				x = pq1.peek().i;
				v += b;
			} else {
				System.out.println(x + " " + v);
			}
		}
	}

	static class Int2 implements Comparable<Int2> {
		int i;

		public int compareTo(Int2 o) {
			return o.i - i;
		}
	}
}



Measured memory_bytes: 71888
#include <stdio.h>

int main(void)
{
  long long N, M;
  
  scanf("%lld %lld", &N, &M);
  
  if(2 * N > M) printf("%lld\n", M / 2);
  else printf("%lld\n", N + (M - 2 * N) / 4);
  
  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <set>

using namespace std;

int main() {
    int n;
    set<int> st;
    cin >> n;
    for (int i = 0; i < n; i ++){
        int x; cin >> x;
        if (st.find(x) != st.end()){
            cout << "NO" << endl;
            return 0;
        }
        st.insert(x);
    }
    cout << "YES" << endl;
    return 0;
}


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

const ll INF = 1LL << 60;

ll N;
vector<ll> a;

int main() {
    cin >> N;
    a.resize(3 * N);
    rep(i, 3 * N) {
        cin >> a[i];
    }

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

    ll ans = 0;
    // 第2グループから2つずつとる
    for (int i = N; i <= 3 * N - 1; i+= 2) {
        // cout << i << endl;
        ans += a[i];
    }

    cout << ans << endl;
}

Measured memory_bytes: 2560
<?php
fscanf(STDIN, "%d %d %d",$a,$b,$k);
$a_divisor = array();
$b_divisor = array();
$com_divisor = array();
//aの約数を取得
for($i=1;$i<=$a;$i++){
	
	if($a % $i == 0){
			$a_divisor[] = $i;
	}
}
//ｂの約数を取得
for($i=1;$i<=$b;$i++){
	
	if($b % $i == 0){
		$b_divisor[] = $i;
	}
}
//aとbの公約数
for($i=0;$i<count($a_divisor);$i++){
	
	for($n=0;$n<count($b_divisor);$n++){
		
		if ($a_divisor[$i]==$b_divisor[$n]){
			
			$com_divisor[]=$a_divisor[$i];
			break;
		}
	}
}
//k番目に大きいもの
echo $com_divisor[count($com_divisor) - $k];
?>

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

int main(){
  int n;
  cin >> n;
  vector<int> v(n);
  rep(i,n) cin >> v[i];

  int max = 0;
  int min = 1e9;
  rep(i,n){
    if (max < v[i]) max = v[i];
    if (min > v[i]) min = v[i];
  }
  cout << max - min << endl;
  return 0;
}

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

const int MAXN = 30;
int vis[MAXN];
string s;

int main(void){
    int n, m;
    cin >>  n >> m;
    for(int i = 0; i < n; i++){
        cin >> s;
        for(int j = 0; j < m; j++){
            vis[s[j] - 'a']++;
        }
    }
    if(m == 1 && n == 1){
        cout << "Yes" << endl;
        return 0;
    }
    if(n == 1 || m == 1){
        int cnt = 0;
        for(int i = 0; i < 26; i++){
            if(vis[i] & 1) cnt++;
        }
        if(cnt > 1) cout << "No" << endl;
        else cout << "Yes" << endl;
        return 0;
    }
    if(n % 2 == 0 && m % 2 == 0){
        for(int i = 0; i < 26; i++){
            if(vis[i] % 4 == 0) continue;
            else{
                cout << "No" << endl;
                return 0;
            }
        }

    }else if(n & 1 && m % 2 == 0){
        int cnt = 0;
        for(int i = 0; i < 26; i++){
            if(vis[i] & 1){
                cout << "No" << endl;
                return 0;
            }else if(vis[i] % 4 == 0) continue;
            else cnt += vis[i] % 4;
        }
        if(cnt > m){
            cout << "No" << endl;
            return 0;
        }
    }else if(m & 1 && n % 2 == 0){
        int cnt = 0;
        for(int i = 0; i < 26; i++){
            if(vis[i] & 1){
                cout << "No" << endl;
                return 0;
            }else if(vis[i] % 4 == 0) continue;
            else cnt += vis[i] % 4;
        }
        if(cnt > n){
            cout << "No" << endl;
            return 0;
        }
    }else{
        int cnt = 0, gg = 0;
        for(int i = 0; i < 26; i++){
            if(vis[i] % 4 == 0) continue;
            else if((vis[i] % 4) & 1) cnt++, gg += vis[i] % 4;
            else gg += vis[i] % 4;
        }
        if(cnt > 1 || gg > n + m - 1){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))

break_num = 0
counter = 1

for i in range(n):
  if a[i] == counter:
    counter += 1
  else:
    break_num += 1

if break_num == n:
  print(-1)
else:
  print(break_num)

Measured memory_bytes: 26524
#include <iostream>

using namespace std;

typedef long long ll;

int main()
{
  int D,N;
  int cnt = 0;

  cin >> D >> N;

  if ( D == 0 ) {
    if ( N >= 100 ) cout << 101 << endl;
    else cout << N << endl;
  } else {
    ll tmp = 1;
    ll ans = 0;
    for ( int i = 0; i < D; ++i ) tmp *= 100;

    ans = tmp*N;
    if ( N == 100 ) ans += tmp;
    cout << ans << endl;
  }

}


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

long long su[1005];
vector<int> seq;

int main(){
    int n;
    bool non_pos = true;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&su[i]);
        if(su[i]>0) non_pos = false;
    }
    if(non_pos){
        int ans = 1;
        for(int i=2;i<=n;i++){
            if(su[ans] < su[i]) ans = i;
        }
        printf("%lld\n%d\n", su[ans], n-1);
        for(int i=n;i>ans;i--){
            printf("%d\n", i);
        }
        for(int i=1;i<ans;i++){
            printf("%d\n", 1);
        }
    }else{
        long long odd = 0, even = 0;
        for(int i=1;i<=n;i++){
            if(su[i] > 0){
                if(i%2){
                    odd += su[i];
                }else{
                    even += su[i];
                }
            }
        }
        if(odd > even){
            int ss = -1, ee = -1;
            printf("%lld\n", odd);
            for(int i=n;i>=1;i--){
                if(su[i] <= 0 || (i%2) == 0){
                    seq.push_back(i);
                }else{
                    ee = i;
                    break;
                }
            }
            for(int i=1;i<=n;i+=2){
                if(su[i] <= 0){
                    seq.push_back(1);
                    seq.push_back(1);
                }else{
                    ss = i;
                    break;
                }
            }
            for(int i=ss+2;i<=ee;i+=2){
                if(su[i] <= 0){
                    seq.push_back(3);
                }else{
                    seq.push_back(2);
                }
            }
        }else{
            int ss = -1, ee = -1;
            printf("%lld\n", even);
            for(int i=n;i>=1;i--){
                if(su[i] <= 0 || (i%2) == 1){
                    seq.push_back(i);
                }else{
                    ee = i;
                    break;
                }
            }
            seq.push_back(1);
            for(int i=2;i<=n;i+=2){
                if(su[i] <= 0){
                    seq.push_back(1);
                    seq.push_back(1);
                }else{
                    ss = i;
                    break;
                }
            }
            for(int i=ss+2;i<=ee;i+=2){
                if(su[i] <= 0){
                    seq.push_back(3);
                }else{
                    seq.push_back(2);
                }
            }
        }
        printf("%d\n", seq.size());
        for(auto &elem: seq) printf("%d\n", elem);
    }
}


Measured memory_bytes: 256
s = input()

for i in range(len(s)):
    if i % 2 ==0:
        if s[i] == "R" or s[i] == "U" or s[i] == "D":
            ans = "Yes"
        else:
            ans = "No"
            break
    elif i % 2 ==1:
        if s[i] =="L" or s[i] == "U" or s[i] == "D":
            ans = "Yes"
        else:
            ans = "No"
            break
print(ans)

Measured memory_bytes: 3064
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Globalization;
using System.Diagnostics;
using Pair = System.Collections.Generic.KeyValuePair<int, int>;

class Program
{
    static void Main()
    {
        Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });
        new Program().Solve();
        Console.Out.Flush();
    }
    Scanner cin = new Scanner();


    void Solve()
    {
        int n = cin.Nextint, q = cin.Nextint;
        var d = new BIT(n);
        for (int i = 0; i < q; i++)
        {
            if (cin.Nextint == 0)
            {
                int a = cin.Nextint, b = cin.Nextint, x = cin.Nextint;
                d.Add(a, x);
                d.Add(b + 1, -x);
            }
            else
            {
                Console.WriteLine(d.Sum(cin.Nextint));
            }
        }
    }

}
class BIT //[1, n]
{
    int n;
    int[] bit;

    public BIT(int N)
    {
        n = N;
        bit = new int[n + 1];
    }

    public void Add(int i, int x)
    {
        while (i <= n)
        {
            bit[i] += x;
            i += i & -i;
        }
    }

    // [1, i] sum
    public int Sum(int i)
    {
        int s = 0;
        while(i > 0)
        {
            s += bit[i];
            i -= i & -i;
        }
        return s;
    }

    //[a, b] sum
    public int Sum(int a, int b)
    {
        return Sum(b) - Sum(a - 1);
    }
}
class Scanner
{
    string[] s; int i;
    char[] cs = new char[] { ' ' };
    public Scanner() { s = new string[0]; i = 0; }
    public string[] Scan { get { return Console.ReadLine().Split(); } }
    public int[] Scanint { get { return Array.ConvertAll(Scan, int.Parse); } }
    public long[] Scanlong { get { return Array.ConvertAll(Scan, long.Parse); } }
    public double[] Scandouble { get { return Array.ConvertAll(Scan, double.Parse); } }
    public string Next
    {
        get
        {
            if (i < s.Length) return s[i++];
            string st = Console.ReadLine();
            while (st == "") st = Console.ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            i = 0;
            return Next;
        }
    }
    public int Nextint { get { return int.Parse(Next); } }
    public long Nextlong { get { return long.Parse(Next); } }
    public double Nextdouble { get { return double.Parse(Next); } }
}

Measured memory_bytes: 10120
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		// fizzbuzz

		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();

		sc.close();

		for(int i=1; i<=n; i++) {
			// 3または3を含む数字を出力する
			if(i % 3 == 0) {
				System.out.print(" " + i);
			} else if(String.valueOf(i).indexOf("3") >= 0) {
				System.out.print(" " + i);
			}
		}
		System.out.println("");

	}

}



Measured memory_bytes: 29288
#include<iostream>
#include<vector>
#include<algorithm>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;

int main(){
	int n;
	cin>>n;
	vector<int>a(n);
	rep(i,n)cin>>a[i];
	int q;
	cin>>q;
	vector<int>b(q),c(q);
	rep(i,q){
		cin>>b[i]>>c[i];
	}
	long long int sum=0;
	rep(i,n)sum+=a[i];
	vector<int>map(100001,0);
	rep(i,n)map[a[i]]+=1;
	rep(i,q){
		sum+=map[b[i]]*(c[i]-b[i]);
		cout<<sum<<endl;
		map[c[i]]+=map[b[i]];
		map[b[i]]=0;
	}


	return 0;
}

Measured memory_bytes: 4812
#include<bits/stdc++.h>
#define MOD 1000000007
#define ll long long
#define mp make_pair
#define pb push_back 
#define N 21
using namespace std;
int dp[N][1 << 21], A[N][N], n;
ll fun(int a, int mask){
	if(a == n)
		return 1;
	if(dp[a][mask] != -1)
		return dp[a][mask];
	ll ans = 0;
	for(int i = 0; i < n; i++){
		if(!(mask & (1 << i)) && A[a][i]){
			ans = (ans + fun(a + 1, mask | (1 << i))) % MOD;
		}
	}
	return dp[a][mask] = ans;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			cin >> A[i][j];
	memset(dp, -1, sizeof(dp));
	cout << fun(0, 0) << '\n';


}

Measured memory_bytes: 172288
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define ll long long
#define lld long double
#define ALL(x) x.begin(), x.end()
#ifdef DEBUG
#define line() cerr << "[" << __LINE__ << "] ";
#define dump(i) cerr << #i ": " << i << " ";
#define dumpl(i) cerr << #i ": " << i << endl;
#else
#define line(i)
#define dump(i)
#define dumpl(i)
#endif
using namespace std;

int main(int argc, char const *argv[])
{

    int a, b;
    cin >> a >> b;
    if (a == b)
        cout << (2 * a) << endl;
    else
        cout << 2 * max(a, b) - 1 << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <algorithm>
#define _USE_MATH_DEFINES
#include <cmath>
#include <numeric>
#include <iomanip>
#include <deque>
#include <tuple>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <sstream>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>

#define rep(i, x) for (int i = 0; i < (int)(x); i++)
#define FOR(i, a, done) for (int i = (a); i < (done); ++i)
#define all(a) (a).begin(), (a).end()
#define F first
#define S second
#define pb push_back
#define pf push_front

namespace mp = boost::multiprecision;
using cpp_int = mp::cpp_int;
using ll = long long;
using namespace std;

ll M = 1000000007;
typedef pair<int, int> P;

int main()
{
    int h, w;
    cin >> h >> w;
    vector<string> a(h);
    rep(i, h) cin >> a[i];
    vector<int> al(26);
    vector<vector<bool>>done(h,vector<bool>(w,false));
    int cnt4=0,cnt2=0,cnt1=0;
    rep(i, h) rep(j, w)
    {
        int m = a[i][j] - 'a';
        al[m]++;
    }
    rep(i,h)rep(j,w){
        if(!done[i][j]){
            int cnt=1;
            done[i][j]=true;
            if(!done[h-1-i][j]){
                done[h-1-i][j]=true;
                cnt++;
            }
            if(!done[h-1-i][w-1-j]){
                done[h-1-i][w-1-j]=true;
                cnt++;
            }
            if(!done[i][w-1-j]){
                done[i][w-1-j]=true;
                cnt++;
            }
            if(cnt==4){
                cnt4++;
            }else if(cnt==2){
                cnt2++;
            }else if(cnt==1){
                cnt1++;
            }
        }
    }
    bool ok = true;
    rep(i,26){
        if(cnt4>0){
            if(al[i]>=4){
                int tmp=al[i]/4;
                if(cnt4>=tmp){
                    cnt4-=tmp;
                    al[i]-=4*tmp;
                }else{
                    al[i]-=cnt4*4;
                    cnt4=0;
                }
                
            }
        }
        if(cnt2>0){
            if(al[i]>=2){
                int tmp=al[i]/2;
                if(cnt2>=tmp){
                    cnt2-=tmp;
                    al[i]-=tmp*2;
                }else{
                    al[i]-=cnt2*2;
                    cnt2=0;
                }
            }
        }
        if(cnt1>0){
            if(al[i]>=1){
                if(cnt1>=al[i]){
                    cnt1-=al[i];
                    al[i]=0;
                }else{
                    al[i]-=cnt1;
                    cnt1=0;
                }
            }
        }
    }  
    if(cnt4==0&&cnt2==0&&cnt1==0){

    }else{
        ok=false;
    }
    if (ok)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
}


Measured memory_bytes: 256
D,G = map(int,input().split())
PC = [0]+[list(map(int,input().split())) for _ in range(D)]
def f(i,t):
    if i == 0 or i > D:
        return 10**9
    k = min(t//(100*i),PC[i][0])
    s = 100*i*k
    if k == PC[i][0]:
        s += PC[i][1]
    if s<t:
        k += f(i-1,t-s)
        #k += min(f(i-1,t-s),f(i+1,t-s))
    return min(k,f(i-1,t))

print(f(D,G))

Measured memory_bytes: 3064