akhauriyash/Code-Regression huggingface dataset:
import sys
import bisect
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

s = S()
t = S()
N = len(s)

dic = {}

for i in range(N):
  if s[i] in dic:
    dic[s[i]].append(i+1)
  else:
    dic[s[i]] = [i+1]

tmp = 0
cnt = 0
for i in t:
  if i not in dic:
    print(-1)
    exit()
  else:
    l = dic[i]
    n = bisect.bisect_left(l,tmp)
    if n > len(l)-1:
      tmp = l[0]
      cnt += 1
    else:
      if tmp == l[n]:
        n += 1
        if n > len(l)-1:
          tmp = l[0]
          cnt += 1
        else:
          tmp = l[n]
      else:
        tmp = l[n]

print(cnt*N+tmp)


Measured memory_bytes: 46044
n = gets.to_i
max = 0
num = 1
(1..n).each do |i|
  j = i
  if i % 2 == 0
    count = 0
    while j % 2 == 0
      j /= 2
      count += 1
    end
    if max < count
      max = count
      num = i
    end
  end
end
puts num

Measured memory_bytes: 1788
def solve(string):
    n, *a = map(int, string.split())
    m = 10**9 + 7
    ans = 0
    for s in map(lambda x: x.count("1"), zip(*("{:060b}".format(_a) for _a in a))):
        ans <<= 1
        ans += s * (n - s)
        ans %= m
    return str(ans)


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))


Measured memory_bytes: 82536
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<utility>
#include<tuple>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<iomanip>
#include<numeric>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define BIL ((ll)1e9)
#define MOD ((ll)1e9+7)
#define INF (1LL<<60)           //1LL<<63でオーバーフロー
#define inf (1<<29)             //1<<29でオーバーフロー

int main(int argc,char* argv[]){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);

    string s;
    cin >> s;
    int n=s.size()+1;

    vector<int> a(n);
    for(int i=0;i<n-1;i++){
        if(s[i]=='<'){
            if(a[i+1]<a[i]+1)a[i+1]=a[i]+1;
        }
    }
    for(int i=n-2;i>=0;i--){
        if(s[i]=='>'){
            if(a[i]<a[i+1]+1)a[i]=a[i+1]+1;
        }
    }

    ll sum=0;
    for(int i=0;i<n;i++){
        sum+=a[i];
    }

    cout << sum << endl;

    // Wrong Answer
    // a[0]=0;
    // int begin=0,minus=0,sum=0;
    // for(int i=0;i<s.size();i++){
    //     if(s[i]=='<'){
    //         sum+=a[i]+1;
    //         a[i+1]=a[i]+1;
    //         if(begin!=0){
    //             if(a[begin]<=minus){
    //                 sum=sum-a[begin]+minus+1;
    //             }
    //             begin=0;
    //             minus=0;
    //         }
    //     }else{
    //         if(begin==0){
    //             begin=i;
    //         }
    //         sum+=minus;
    //         minus++;
    //     }
    // }

    // cout << sum << endl;

    return 0;
}


Measured memory_bytes: 5872
#!/usr/bin/env python3
import sys

def solve(N: int, T: int, A: "List[int]", B: "List[int]"):
    dp = [0] * (T + 1)
    for a, b in sorted(zip(A, B), reverse=True):
        for t in range(T):
            dp[t] = max(dp[t],
                        b + (dp[t+a] if t + a < T else 0))
    return max(dp)

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    print(solve(N, T, A, B))

if __name__ == '__main__':
    main()


Measured memory_bytes: 43228
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static Scanner in = new Scanner(System.in);
	public static void main(String[] args) {
		int N = in.nextInt();;
		int[] t = new int[3 * N];
		for(int i = 0; i < 3 * N; i++){
			t[i] = in.nextInt();
		}
		Arrays.sort(t);
		long sum = 0;
		for(int i = 0; i < 2 * N; i += 2){
			sum += t[N + i];
		}
		System.out.println(sum);
	}
}


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

using namespace std;

#define Rep(i,a,b)  for (int i=(a);i<(b);i++)
#define rep(i,n)    for (int i=0;i<(n);i++)
#define all(x)      (x).begin(), (x).end()

#define ll long long

int main()
{
	int n, k;
	cin >> n >> k;
	int count = 0;
	Rep(i, 1, n + 1)
		if (i % k == 0)
			count++;
	ll ans = pow(count, 3);
	count = 0;
	if (k % 2 == 0)
		Rep(i, 1, n + 1)
			if (i % k == k / 2)
				count++;
	ans += pow(count, 3);

	cout << ans << endl;
}



Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
        long[] x = new long[N];
		long[] y = new long[N];
    	for(int i = 0; i < N; i++){
    		x[i] = sc.nextLong();
			y[i] = sc.nextLong();
    	}
    	
		long maxZ = Long.MIN_VALUE;
		long minZ = Long.MAX_VALUE;
		long maxW = Long.MIN_VALUE;
		long minW = Long.MAX_VALUE;
		
		for (int i = 0; i < N; i++) {
			long z = x[i] + y[i];
			long w = x[i] - y[i];
			
			if (maxZ < z) {
			    maxZ = z;
			}
			if (z < minZ) {
			    minZ = z;
			}
			if (maxW < w) {
			    maxW = w;
			}
			if (w < minW) {
			    minW = w;
			}
		}
        
		System.out.println(Math.max(maxZ - minZ, maxW - minW));
	}
}

Measured memory_bytes: 63484
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define cinf(n,x) for(int i=0;i<(n);i++)cin>>x[i];
#define ft first
#define sc second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define LB(a,x) lb(all(a),x)-a.begin()
#define UB(a,x) ub(all(a),x)-a.begin()
#define mod 1000000007
//#define mod 998244353
#define FS fixed<<setprecision(15)
using namespace std;
typedef long long ll;
const double pi=3.141592653589793;
template<class T> using V=vector<T>;
using Graph = vector<vector<int>>;
using P=pair<ll,ll>;
typedef unsigned long long ull;
typedef long double ldouble;
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; }
template<class T> inline void out(T a){ cout << a << '\n'; }
void YN(bool ok){if(ok) cout << "Yes" << endl; else cout << "No" << endl;}
//void YN(bool ok){if(ok) cout << "YES" << endl; else cout << "NO" << endl;}


const ll INF=1e18;
const int mx=200005;

int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    int h,w;
    cin>>h>>w;
    V<int> a(26,0);
    rep(i,h) rep(j,w){
        char c;
        cin>>c;
        a[c-'a']++;
    }
    bool ok=1;
    if((h*w)%2==0){
        rep(i,26) if(a[i]%2==1) ok=0;
    }else{
        int cnt=0;
        rep(i,26) if(a[i]%2==1) cnt++;
        if(cnt!=1) ok=0;
        if(ok){
            rep(i,26){
                if(a[i]%2==1) a[i]--;
            }
        }
    }
    if(ok){
        int c4=0,c2=0;
        rep(i,26){
            if(a[i]>0){
                if(a[i]%4==0) c4++;
                else if(a[i]%2==0) c2++;
            }
        }
        int ma=0;
        if(h%2==1) ma+=w/2;
        if(w%2==1) ma+=h/2;
        if(c2>ma) ok=0;
        else if((ma-c2)%2==1) ok=0;
    }
    YN(ok);
}

Measured memory_bytes: 3640
#include<iostream>
#include<sstream>
#include<vector>
#include<iterator>
#include<algorithm>
#include<numeric>
using namespace std;

int main(void)
{
    int N, K;
    cin >> N >> K;

    vector<int> V(N);
    for (int i = 0; i < N; i++)
        cin >> V[i];

    int ans = 0;
    for (int i = 0; i <= K; i++) {
        for (int j = 0; j <= K - i; j++) {
            if (i + j > N)
                break;
            
            vector<int> item;
            for (int k = 0; k < i; k++)
                item.push_back(V[k]);
            for (int k = 0; k < j; k++)
                item.push_back(V[N - 1 - k]);

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

            for (int k = 0; k < K - i - j; k++) {
                if (k >= (int)item.size())
                    break;

                if (item[k] < 0)
                    item[k] = 0;
            }

            int sum = accumulate(item.begin(), item.end(), 0);
            ans = max(ans, sum);
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define c(P)        cout<<P<<"\n"
#define pii         pair<ll,ll>
#define mi          map<ll,ll>
#define mii         map<pii,ll>
#define F           first
#define S           second
#define mem(a,val)  memset(a,val,sizeof(a))
#define fr(i,x,n)   for(ll i=x;i<n;i++)
#define frr(i,x,n)  for(ll i=n-1;i>=x;i--)


const ll N   =  500005;
const ll mod = 1e9 + 7;

using namespace std;


void solve(){

  ll x=0,y=0,c=0,ans=0;
  ll n,m,k;
  cin>>n>>m;
  if(n<m)
  {
  k = m;
  while(k--)
  {
    x= x*10+ n;
  }
  c(x);
    }
    else
    {
  k =n;
  while(k--)
  {
    y= y*10+ m;
  }
  c(y);
}
}

signed main(){
     
  ios_base::sync_with_stdio(false);   
  cin.tie(NULL);
  ll T=1;
  //cin>>T;
  while(T--){
  solve();
  }
  return 0;
}


Measured memory_bytes: 256
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    mod = 10**9 + 7

    s = input().rstrip()
    n = len(s)
    dp = [[0]*13 for _ in range(n)]

    if s[-1]=='?':
        for i in range(10):
            dp[0][i] = 1
    else:
        a = int(s[-1])
        dp[0][a] = 1

    a = 1
    for i in range(1, n):
        a = 10 * a % 13
        if s[-(i+1)] == '?':
            for j in range(10):
                for k in range(13):
                    dp[i][(a*j+k)%13] += dp[i-1][k] % mod
        else:
            j = int(s[-(i+1)])
            for k in range(13):
                dp[i][(a*j+k)%13] += dp[i-1][k] % mod
    print(dp[-1][5]%mod)


if __name__ == '__main__':
    main()

Measured memory_bytes: 61788
import sys
from collections import Counter
def I(): return int(sys.stdin.readline().rstrip())
def S(): return sys.stdin.readline().rstrip()

N = I()
S_list = [S() for i in range(N)]

counter = Counter()
for ss in S_list:
    counter[ss] += 1

for ss in ["AC", "WA", "TLE", "RE"]:
    print("{} x {}".format(ss, counter[ss]))

Measured memory_bytes: 16620
#define rep(i, n) for (int i = 0; i < (n); i++)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int MOD = 1000000007;
// MAX int 2,147,483,647
// MAX O(n) 10^18

int main() {
    int N;
    cin >> N;
    vector<int> d(N);
    rep(i, N) cin >> d.at(i);

    int ans = 0;
    for (int i = 0; i < N - 1; i++) {
        for (int j = i + 1; j < N; j++) {
            ans += d.at(i) * d.at(j);
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3568
#include<cstdio>

using namespace std;

int d, n;

int main(){
	scanf("%d%d", &d, &n);
	if(n == 100)	printf("101");
	else	printf("%d", n);
	for(int i = 1; i <= d; i++)
		putchar('0'), putchar('0');
	putchar(10);
	return 0;
}


Measured memory_bytes: 128
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ans = 0
for i in range(N):
  if A[i] <= B[i]:
    ans += A[i]
    B[i] -= A[i]
    A[i] = 0
    ans += min(A[i + 1], B[i])
    A[i + 1] = max(A[i + 1] - B[i], 0)
  else:
    ans += B[i]
print(ans)

Measured memory_bytes: 18624
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>

using namespace std;
#define i64  long long

#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807

void solve(void)
{

  vector<string> vec_str;
  string str;
  while(getline(cin,str))
  {
    vec_str.push_back(str);
  }
  
  vector<int> counter (26,0);

  char check_L = 'A';
  char check_S = 'a';

  for (int i = 0; i <= 25; i++)
  {
    for (int j = 0; j < vec_str.size(); j++)
    {
    for (int c = 0; c < vec_str[j].size(); c++)
    {
      if((vec_str[j][c] == check_L + i) || (vec_str[j][c] == check_S + i)  ) counter[i]++;
    }
    }
    

  }
  
  for (int i = 0; i <= 25; i++)
  {
    cout<<char(check_S + i)<<" "<< ":" << " "<<counter[i]<<endl;
  }
  

  
  return;
}

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

  solve();

  return 0;
}



Measured memory_bytes: 3184
// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>
#include <cstring>

#define ll long long
#define Int ll
#define loop(__x, __start, __end) for(Int __x = __start; __x < __end; __x++)
#define loopdown(__x, __start, __end) for(Int __x = __start; __x > __end; __x--)
#define rep(__n) for(Int __x = 0; __x < __n; __x++)
#define span(__a,__x,__y) __a.begin()+__x,__a.begin()+__y
#define span_all(__a) __a.begin(),__a.end()
#define len(__x) (__x.size())
#define last(__x) (__x[__x.size()-1])

using namespace std;

struct Point {
  Int x, y;
  Point(Int x, Int y): x(x), y(y) {}
  Point(): x(0), y(0) {}

  Point operator + (Point v) { return Point(x + v.x, y + v.y); }
  Point operator - (Point v) { return Point(x - v.x, y - v.y); }
  bool operator == (const Point &v) const {
    return x == v.x && y == v.y;
  }
  bool operator< (const Point &p1) const {
    return x < p1.x && y < p1.y;
  }
};
ostream & operator << (ostream & out, Point const & v) {
  out << "Point(" << v.x << ", " << v.y << ')';
  return out;
}

istream & operator >> (istream & in, Point & v) {
  Int x, y;
  in >> x; in >> y; v.x = x; v.y = y;
  return in;
}

// Geometry

#define EPS 0.0000000001

class Vector2 {
public:
  double x, y;
  
  Vector2(double x = 0, double y = 0): x(x), y(y) {}
  
  Vector2 operator + (Vector2 v) { return Vector2(x + v.x, y + v.y); }
  Vector2 operator - (Vector2 v) { return Vector2(x - v.x, y - v.y); }
  Vector2 operator * (double k) { return Vector2(x * k, y * k); }
  Vector2 operator / (double k) { return Vector2(x / k, y / k); }
  
  double length() { return sqrt(norm()); }
  double norm() { return x * x + y * y; }
  double dot (Vector2 v) { return x * v.x + y * v.y; }
  double cross (Vector2 v) { return x * v.y - y * v.x; }
  
  bool operator < (const Vector2 &v) const {
    return x != v.x ? x < v.x : y < v.y;
  }
  
  bool operator == (const Vector2 &v) const {
    return fabs(x - v.x) < EPS && fabs(y - v.y) < EPS;
  }
};

ostream & operator << (ostream & out, Vector2 const & v) { 
  out<< "Vector2(" << v.x << ", " << v.y << ')';
  return out;
}

istream & operator >> (istream & in, Vector2 & v) { 
  double x, y;
  in >> x;
  in >> y;
  v.x = x;
  v.y = y;
  return in;
}

Int N;
vector<Int> A;

void input() {
  cin >> N;
}

void solve() {
  cout << (N/2 + N%2) << endl;
}

int main() {
  input();
  solve();
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

int main() {
	int n; scanf("%d", &n); std::vector<int> a(n);
	for(int i = 0; i < n; i++) scanf("%d", &a[i]);

	i64 ans = 0;
	for(int i = 0, A = 0, B = 0, cur = 0; i < n; i++) {
		while(cur < a.size() and ((A + a[cur]) == (B ^ a[cur]))) {
			A += a[cur];
			B ^= a[cur];
			cur++;
		}
		if(A == B) ans += (i64)cur - i;

		A -= a[i];
		B ^= a[i];
	}
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i < (n); ++i)
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;}
using namespace std;
using ll = long long;
using P = pair<int,int>;
using Pl = pair<long long,long long>;
using veci = vector<int>;
using vecl = vector<long long>;
using vecveci = vector<vector<int>>;
using vecvecl = vector<vector<long long>>;

int main() {
    int D; cin >> D;
    veci C(26);
    vecveci S(D,veci(26));
    veci T(D);
    REP(i,26) cin >> C[i];
    REP(i,D) REP(j,26) cin >> S[i][j];
    REP(i,D) cin >> T[i];
    veci last(26);
    ll ans = 0;
    REP(i,D) {
        int d = i+1;
        last[T[i]-1] = d;
        ans += S[i][T[i]-1];
        REP(j,26) {
            ans -= C[j]*(d-last[j]);
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 3640
X,N = map(int,input().split())
p = [int(i) for i in input().split()]
if N==0:
    print(X)
else:
    pN=[]
    for j in range(N):
        pj = p[j]-X
        pN.append(pj)
    pN.sort()
    p0 = pN[0]-1
    p1 = pN[N-1]+1
    list_p = list(range(p0,p1+1,1))
    result = list(set(list_p)-set(pN))
    k0 = abs(result[0])
    for k in result:
        k1 = abs(k)
        if k1<k0:
            k0 = k1
    cnt = 0
    for l in result:
        if l == (-1)*k0:
            cnt+=1
    if cnt==0:
        print(X+k0)
    else:
        print(X-k0)

Measured memory_bytes: 9208
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        double r = sc.nextDouble();
        double pi = Math.PI;

        double area = pi*r*r;
        double length = 2*pi*r;

        System.out.printf("%f %f",area,length);
        sc.close();
    }
}


Measured memory_bytes: 28424
# -*- coding: utf-8 -*-
# 整数の入力
n, m = map(int, raw_input().split())

dic = {} # yen: many

for i in range(n):
    a, b = map(int, raw_input().split())
    if a in dic: dic[a] += b
    else: dic.update({a:b})

dic = sorted(dic.items())

count = 0
yen = 0
for k, v in dic:

    if v < m-count:
        yen += k*v
        count += v
    else:
        yen += k*(m-count)
        count += m-count
        print yen
        break


Measured memory_bytes: 23840
#include <iostream>
#include <string>
#include <vector>
#include <iomanip>


int main(void){
  long w, h, x, y;
  std::cin >> w >> h >> x >> y;

  bool flag = (x*2==w) && (y*2==h);

  std::cout << std::setprecision(10)
            << (w*h)/2.0 << " "
            << (flag ? 1 : 0)
            << std::endl;


  return 0;
}

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

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

    string s;
    cin >> s;
    string word = "keyence";

    for (unsigned long i = 0; i <= 7; ++i) {
        if (s.substr(0, i) == word.substr(0, i)
            && s.substr(s.length() - 7 + i, 7 - i) == word.substr(i, 7 - i) ) {
            cout << "YES" << '\n';
            return 0;
        }

    }
    cout << "NO" << '\n';
    return 0;
}


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

int main() {

  int N;
  cin >> N;

  bool answer = false;
  for (int i = 1; i <= 9; i++) {
    for (int j = 1; j <= 9; j++) {
      if (i * j == N) {
        answer = true;
      }
    }
  }

  if (answer) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }

}


Measured memory_bytes: 256
def get_lcs_table(s1, s2):
    l1, l2 = len(s1)+1, len(s2)+1
    dp = [[0]*l2 for _ in range(l1)]
    for i in range(l1):
        for j in range(l2):
            dp[i][j] = 0 if i==0 or j==0 else dp[i-1][j-1]+1 if s1[i-1]==s2[j-1] else max(dp[i][j-1], dp[i-1][j])
    return dp


def restore_lcs(s1, s2, dp):
    x, y = len(s1), len(s2)
    l = []
    while x and y:
        if dp[x][y] == dp[x-1][y]:
            x -= 1
        elif dp[x][y] == dp[x][y-1]:
            y -= 1
        else:
            x -= 1
            y -= 1
            l.append(s1[x])
    return "".join(l[::-1])


if __name__ == "__main__":
    s = input()
    t = input()
    dp = get_lcs_table(s, t)
    print(restore_lcs(s, t, dp))


Measured memory_bytes: 111708
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<map>
using namespace std;
const int maxn = 2e5+10;

int read(){
	int x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+c-48;c=getchar();}
	return x*f;
}

int k,m,n;
double a[maxn];
int main(){
	n=read();k=read();
	for(register int i=1;i<=n;i++){
		a[i]=read();
		a[i]=1.0*(a[i]+1)/2;
	}
	double ans=0,sum=0;
	for(register int i=1;i<=k;i++)sum+=a[i];
	ans=sum;
	for(register int i=k+1;i<=n;i++){
		sum+=a[i];sum-=a[i-k];
		ans=max(sum,ans);
	}
	printf("%.7lf\n",ans);
	return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
int main(){
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> x(n),y(n);
    rep(i,n) cin >> x[i] >> y[i];
    auto dist = [&](int i, int j)->double{
        int dx = x[i]-x[j];
        int dy = y[i]-y[j];
        return sqrt(dx*dx+dy*dy);
    };
    vector<int> perm(n);
    rep(i,n) perm[i] = i; //1-n-1
    double ave = 0;
    int perm_num = 0;
    do {
        perm_num++;
        double dist_sum = 0;
        rep(i, n-1) dist_sum+=dist(perm[i], perm[i+1]);
        ave+=1.0*dist_sum;
    } while(next_permutation(perm.begin(), perm.end()));
    ave /= perm_num;
    printf("%.10lf\n",ave);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <typeinfo>
#include <cxxabi.h>
#ifdef LOCAL
#include "dbgtoki.hpp"
#define DUMP(i) dump((string)TOSTRING(i), demangle(typeid(i).name()), __LINE__ , i) 
#else
#define DUMP(i)
#endif

using namespace std;
#define TOSTRING(x) #x
#define SZ(x) (int)(x).size()
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(s) (s).begin(), (s).end()
#define dis distance
#define so(V) sort(ALL(V))
#define rev(V) reverse(ALL(V))
#define uni(v) v.erase( unique(ALL(v)) , v.end());
#define pub push_back
#define sec second
#define fir first

typedef long long unsigned int llu;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector <int> > vvi;
const int EPS = 1e-9;
const int MOD = 1e9+7;
const int INF = (1 << 30);
const double PI = acos(-1);

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,c,k;
	cin >> n >> c >> k;
	vi T(n);
	REP(i,n)cin >> T[i];
	so(T);
	int waitT = 0;//バスに一番最初に乗った人が待てる時間
	int ans = 0;
	int busp = 0;//バスに乗っている人
	REP(i,n){
		if(waitT < T[i]){
			ans++;
			waitT = T[i] + k;
			busp = 0;
		}
		if(busp == c){
			ans++;
			waitT = T[i] + k;
			busp = 0;
		}
		busp++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int main(){
	int a[3];
	cin>>a[0]>>a[1]>>a[2];
	sort(a,a+3);
	if(a[0]==5&&a[1]==5&&a[2]==7){
		cout<<"YES"<<endl;
	}
	else cout<<"NO"<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <iterator>
using namespace std;

/*
const int MAX=1000;
vector<vector<int> > memo(MAX,vector<int>(MAX));
vector<vector<int> > done(MAX,vector<int>(MAX));
int dfs(vector<vector<int> > vi,int i,int j,int sum);

int main(){
	//ios::sync_with_stdio(false);
	//cin.tie(0);
	int m,n;
	while(cin>>m>>n&&m!=0&&n!=0){
		vector<vector<int> > ice(m,vector<int>(n));
		int ans=0;
		for(int i=0; i<MAX; ++i){
			for(int j=0; j<MAX; ++j){
				memo[i][j]=0;
				done[i][j]=0;
			}
		}
		for(int i=0; i<n; ++i){
			for(int j=0; j<m; ++j){
				cin >> ice[j][i];
			}
		}
		for(int i=0; i<n; ++i){
			for(int j=0; j<m; ++j){
				if(ice[i][j]==1) {
					ans=max(ans,dfs(ice,i,j,0));
				}
			}
		}
		cout << ans << "\n";
	}
	return 0;
}

int dfs(vector<vector<int> > vi,int i,int j,int sum){
	if(done[i][j]==1) return memo[i][j];
	if(i+1>=vi.size()&&j+1>=vi[i].size()&&i-1<0&&j-1<0&&vi[i+1][j]==0&&vi[i][j+1]==0&&vi[i-1][j]==0&&vi[i][j-1]==0) return sum;
	done[i][j]=1;
	++sum;
	if(i+1<vi.size()) memo[i][j]=dfs(vi,i+1,j,sum+1);
	if(j+1<vi[i].size()) memo[i][j]=dfs(vi,i,j+1,sum+1);
	if(i-1>=0) memo[i][j]=dfs(vi,i-1,j,sum+1);
	if(j-1>=0) memo[i][j]=dfs(vi,i,j-1,sum+1);
	return memo[i][j]; 
}
*/

int main(){
	int l,a,b,c,d;
	cin >> l >> a >> b >> c >> d ;
	int ans=l-max((a+c-1)/c,(b+d-1)/d);
	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 1164
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define ALL(x) (x).begin(), (x).end()
#define REP(i ,n) for(int i = 0; i < (int)(n); i++)
#define pb push_back
typedef vector<int>vint;
typedef vector<ll>vll;
template<typename T> istream &operator>>(istream &is, vector<T> &vec){ for (auto &v : vec) is >> v; return is; }
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

// 深さ優先探索
vll score;
void dfs(const Graph &G, int v, int p) {
  if(p != -1) score[v] += score[p];
  // v から行ける各頂点 next_v について
  for (auto next_v : G[v]) {
    if(next_v != p) dfs(G, next_v, v); // 再帰的に探索
  }
}

int main()
{
  int N,Q;
  cin >> N >> Q;
  
  Graph G(N);
  
  REP(i,N-1){
    int a,b;
    cin >> a >> b;
    a--;
    b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  score.assign(N, 0);
  REP(i,Q){
    int p,x;
    cin >> p >> x;
    p--;
    score[p] += x;
  }
  dfs(G,0,-1);
  for(auto s :score){
    cout << s << " ";
  }
  cout << endl;
}

Measured memory_bytes: 24320
// 6/13
// 3-2-3. 反転
// 類題
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1e9;

int main() {
    ll N, x;
    cin >> N >> x;

    vector<ll> a(N);
    rep(i, N) cin >> a[i];

    ll res = 0;

    for (ll i = 0; i < N - 1; i++) {
        ll sum = a[i] + a[i + 1];
        if (sum <= x) continue;

        a[i + 1] -= (sum - x);
        if (a[i + 1] < 0) {
            a[i] += a[i + 1];
            a[i + 1] = 0;
        }
        // // i + 1を減らして解決する場合
        // if (a[i + 1] )

        // cout << "here?" << endl;
        // printf("i, sum, a[i], a[i+1] = %d, %d, %d, %d\n", i, sum, a[i], a[i+1]);
        res += (sum - x);
        // printf("sum = %d\n", res);
    }

    cout << res << endl;
}

Measured memory_bytes: 1024
n = int(input())

field = [ [ int(v) for v in input().split() ] for i in range(n) ]
field_2 = [ [ 1 for i in range(n) ] for i in range(n) ]

err = 0
for k in range(n):
    for i in range(n):
        for j in range(n):
            if i != j and j != k and k != i:
                if field[i][k] + field[k][j] == field[i][j]:
                    field_2[i][j] = 0
                if field[i][k] + field[k][j] < field[i][j]:
                    err = 1

if err == 0:
    ans = 0
    for i in range(n):
        for j in range(n):
            ans += field[i][j] * field_2[i][j]
    print(ans//2)
else:
    print(-1)

Measured memory_bytes: 45276
#include<iostream>
#include<vector>
#include<list>
#include<string>
#include<algorithm>
#include<map>
#include<cmath>
using namespace std;
int main() {
	int n;
	cin >> n;
	string a[256];
	for (int i = 0; i < n; i++) cin >> a[i];
	int m;
	cin >> m;
	bool l = false;
	for (int i = 0; i < m; i++) {
		string b;
		cin >> b;
		for (int j = 0; j < n; j++) {
			if (a[j] == b) {
				if (!l) {
					cout << "Opened by " + b << endl;
				}
				else {
					cout << "Closed by " << b << endl;
				}
				l = !l;
				goto stop;
			}
		}
		cout << "Unknown " << b << endl;
	stop:;
	}
} 

Measured memory_bytes: 3152
#include <ctype.h>
#include <float.h>
#include <inttypes.h>
#include <limits.h>
#include <signal.h>
#include <stdarg.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>
#include <math.h>
#ifdef __cplusplus
#include <bits/stdc++.h>
#endif
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")

//char rbuf[]; int rbufl;
//#define getchar() rbuf[rbufl++]
#define getchar getchar_unlocked
#define putchar putchar_unlocked
int32_t nextint(void){ char c=getchar(); while(c!='-'&&(c<'0'||'9'<c)) c=getchar(); bool s=false; if(c=='-'){s=true;c=getchar();} uint32_t x=0; while('0'<=c && c<='9'){ x=x*10+c-'0'; c=getchar(); } return s?-x:x; }
int64_t nextlong(void){ char c=getchar(); while(c!='-'&&(c<'0'||'9'<c)) c=getchar(); int s=0; if(c=='-'){s=1;c=getchar();} uint64_t x=0; while('0'<=c && c<='9'){ x=x*10+c-'0'; c=getchar(); } return s?-x:x; }
uint32_t nextstr(char *s){ char c=getchar(); while(c==' '||c=='\n') c=getchar(); uint32_t len=0; while(c!=' '&&c!='\n'){ *s++=c; len++; c=getchar(); } *s='\0'; return len; }
void printint(int32_t x){ if(x<0){x=-x; putchar('-');}else if(x==0){putchar('0');} int d=0; char s[10]; while(x){ s[d]='0'+x%10; x/=10; d++; } for (int i=d-1; i>=0; i--) putchar(s[i]); putchar('\n'); }
void rsorta_d32(void *base, const int count, const int size, const int index){
	typedef int32_t rsort_t;
	rsort_t (*a)[size] = (rsort_t(*)[size])base;
	rsort_t (*b)[size] = (rsort_t(*)[size])malloc(count*size*sizeof(rsort_t));
	int c[0x100];
	for(int k=0; k<4; k++){
		memset(c, 0, sizeof(c)); for(int i=0; i<count; i++){ c[(a[i][index]>>(k<<3))&0xFF]++; } for(int i=1; i<0x100; i++) c[i]+=c[i-1]; for(int i=count-1; i>=0; i--){ int to=--c[(a[i][index]>>(k<<3))&0xFF]; for(int j=0; j<size; j++){ b[to][j]=a[i][j]; } }{rsort_t(*t)[size]=a; a=b; b=t;}
	}
	free(b);
}

#define P 1000000007
int a[200000];
int main(void){
	int n=nextint();
	for(int i=0; i<n; i++){
		a[i]=nextint();
	}
	int sum=0, sum2=0;
	for(int i=0; i<n; i++){
		sum=(sum+a[i])%P;
		sum2=(sum2+(long)a[i]*a[i]%P)%P;
	}
	int ans = ((long)sum*sum%P+P-sum2)%P;
	ans=ans%2==0?ans/2:(ans+P)/2;
	printf("%d\n", ans);
}


Measured memory_bytes: 2392
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define FOR(i, s, n) for (int i = (s); i < (n); i++)
#define rep(i, n) FOR(i, 0, n)
#define repi(i, n) FOR(i, 1, n + 1)
#define pp(v) cout << #v "=" << (v) << endl;
#define ppa(v) cout << "----\n"; rep(i,v.size()) cout << #v << "[" << i << "] = " << v[i] << endl;
#define div_ceil(a,b) ((a) + ((b) - 1)) / (b)
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
using namespace std;
using Graph = vector<vector<int>>;
using ll = long long;

int main() {
  string e,o;cin>>e>>o;
  rep(i,o.size()) cout << e[i] << o[i];
  if (e.size()!=o.size()) cout << e[e.size()-1] << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define inf 1001001001001001001
#define mod 1000000007
#define mod2 998244353
#define pi acos(-1)
#define all(v) v.begin(),v.end()

ll gcd(ll a,ll b){
    if(b>a) swap(a,b);
    if(b==0) return a;
    return gcd(b,a%b);
}
ll lcm(ll a,ll b){
    ll g=gcd(a,b);
    return a/g*b;
}
ll rep_jijo(ll n,ll x){
    if(x==0) return 1;
    if(x%2==0){
        ll t=rep_jijo(n,x/2);
        return t*t;
    }
    return n*rep_jijo(n,x-1);
}

int main(){
    ll n,k;
    cin >> n >> k;
    vector<ll>a(n);
    vector<ll>f(n);
    rep(i,n) cin >> a[i];
    rep(i,n) cin >> f[i];
    sort(all(a));
    sort(all(f));
    reverse(all(f));
    ll l = -1;
    ll r = 1e12;
    while(1<r-l){
        ll mid =(l+r)/2;
        ll sum=0;
        rep(i,n){
            sum += max(0ll,a[i]-mid/f[i]);
        }
        if(sum<=k) r=mid;
        else l=mid;
    }
    cout << r << endl;
    return 0;
}

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

double c[11] = { 48.00,
				 51.00,
				 54.00,
				 57.00,
				 60.00,
				 64.00,
				 69.00,
				 75.00,
				 81.00,
				 91.00,
				 150.00 };

string s[11] = { "light fly",
				 "fly",
				 "bantam",
				 "feather",
				 "light",
				 "light welter",
				 "welter",
				 "light middle",
				 "middle",
				 "light heavy",
				 "heavy" };

int main() {
	double n;
	while (cin >> n) {
		for (int i = 0; i < 11; i++) {
			if (n <= c[i]) {
				cout << s[i] << endl;
				break;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 3188
class UnionFindTree():

    def __init__(self, n):
        #木全体の要素数
        self.n  = n
        #root[x]<0ならそのノードが根でありその値が木の要素数
        self.root = [-1] * (n+1)
        #ランク
        self.rank = [1] * (n+1)

    def find_root(self,x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]

    def unite(self,x,y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        elif self.rank[x] > self.rank[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def is_same(self,x,y):
        return self.find_root(x) == self.find_root(y)

    def count_node(self,x):
        return -1 * self.root[self.find_root(x)]
from heapq import heapify, heappop

n = int(input())

loc = []
for i in range(n):
    x, y = map(int, input().split())
    loc.append((i , x, y))

sort_x = sorted(loc, key=lambda x:x[1])
sort_y = sorted(loc, key=lambda x:x[2])

diff = []

for i in range(n-1):
    diff.append((sort_x[i+1][1]-sort_x[i][1],sort_x[i][0],sort_x[i+1][0]))
    diff.append((sort_y[i+1][2]-sort_y[i][2],sort_y[i][0],sort_y[i+1][0]))

#最小のものから順番に並べる
heapify(diff)

uft = UnionFindTree(n)

ans = 0
while diff:
    w, s, t = heappop(diff)
    if not uft.is_same(s,t):
        uft.unite(s,t)
        ans += w

print(ans)

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

#define times(n, i) uptil(0, n, i)
#define upto(f, t, i) for(auto _##i = (t), i = decltype(_##i)(f) poi  i <= _##i poi  i++)
#define uptil(f, t, i) for(auto _##i = (t), i = decltype(_##i)(f) poi  i < _##i poi  i++)
#define downto(f, t, i) for(auto i = (f), _##i = decltype(i)(t) poi  i >= _##i poi  i--)
#define downtil(f, t, i) for(auto i = (f), _##i = decltype(i)(t) poi  i > _##i poi  i--)

#define unless(c) if(!(c))
#define until(c) while(!(c))
#define loop while(true)

#define poi ;
#define poipoi << "\n"

/*#define do {*/
/*#define end }*/

#define val const auto
#define var auto

#define zenbu(c) c.begin(), c.end()

#define fuwafuwa(n, c) dokidoki((n) + (c) - 1, c)
#define dokidoki(n, c) ((n) / (c) * (c))

template<class T> bool read(T& t){
    return cin >> t poi
}
template<class T, class...U> bool read(T& t, U&... u){
    unless(cin >> t) return false poi
    return read(u...) poi
}

template<class T> bool equal(T a, T b, T eps = 0){
    return abs(a - b) < eps poi
}

int main(){
    int n poi
    cin >> n poi
    times(n, i){
        double x1, y1, x2, y2, x3, y3, x4, y4 poi
        read(x1, y1, x2, y2, x3, y3, x4, y4) poi
        cout << (equal((x1 - x2) * (y3 - y4), (x3 - x4) * (y1 - y2), 1e-10) ? "YES" : "NO") poipoi poi
    }

    return 0 poi
}

Measured memory_bytes: 1196
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define REP(i,k,n) for(int i = k; i < (int)(n); i++)

#define vi vector<int>
#define pb push_back

typedef long long ll;
using namespace std;


int solve(int num,int now){
    int dis = num - now;

    if(dis == 0) return 1;
    else if(dis > 0) return solve(dis,now + 1);
    else if(dis < 0) return 0;

    return 0;
}
int main(){
    int n;
    while(cin >> n,n) {
        int cnt = 0;
        REP(i,1,n){
            cnt += solve(n,i);
        }
        cout << cnt << endl;
    }


    return 0;
}



Measured memory_bytes: 3068
#include <iostream>

int main() {
  int A, B, C, X, Y;
  std::cin >> A >> B >> C >> X >> Y;

  int answer = 1 << 30;

  answer = std::min(answer, X*A+Y*B);
  answer = std::min(answer, C*2*X+B*std::max(0, Y-X));
  answer = std::min(answer, A*std::max(0, X-Y)+C*2*Y);
  answer = std::min(answer, C*2*std::max(X,Y));

  std::cout << answer << std::endl;
}


Measured memory_bytes: 256
def solver(a, b, c, d, e, f)
  if a * b * d * e != 0
    return ((c - f * (b / e)) / (a - d * (b / e))), ((c - f * (a / d)) / (b - e * (a / d)))
  else
    if a == 0
      return ((f - e * (c / b)) / d), (c / b)
    elsif b == 0
      return (c / a), ((f - d * (c / a)) / e)
    elsif d == 0
      return ((c - b * (f / e)) / a), (f / e)
    else
      return (f / d), ((c - a * (f / d)) / b)
    end
  end
end
def in_triangle?(a, b, c, d, e, f, g, h)
  x, y = solver(h - b, a - g, a * h - b * g, f - d, c - e, c * f - d * e)
  if (e < x and x < c) or (c < x and x < e) or (d < y and y < f) or (f < y and y < d)
    return true
  else
    return false
  end
end
while arg = gets
  arg = arg.split(",").map(&:to_f)
  bool = !in_triangle?(*arg)
  3.times do
    arg.push(*arg.shift(2))
    bool &= !in_triangle?(*arg)
  end
  if bool
    puts "YES"
  else
    puts "NO"
  end
end

Measured memory_bytes: 6148
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		String s = sc.next();

		if (n % 2 == 0) {
			String s1 = s.substring(0, n / 2);
			String s2 = s.substring(n / 2, n);

			if (s1.equals(s2)) {
				System.out.println("Yes");
			} else {
				System.out.println("No");
			}
		} else {
			System.out.println("No");
		}
	}
}

Measured memory_bytes: 22740
/**
 *    author  : 𝒌𝒚𝒐𝒎𝒖𝒌𝒚𝒐𝒎𝒖𝒑𝒖𝒓𝒊𝒏
 *    created : 2020-02-15 07:29:06
**/

#include <iostream>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <complex>
#include <numeric>
#include <bitset>
#include <cassert>
#include <cctype>
#include <iomanip>
#include <random>
#include <utility>
#include <chrono>

using namespace std;

using int64 = long long;

template<class T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec) { os << '{'; size_t n = vec.size(); for (size_t i = 0; i < n; ++i) { os << vec[i]; if (i != n - 1) os << ','; } os << '}'; return os; }
template<class T, class U> std::ostream& operator<<(std::ostream& os, const std::pair<T, U>& p) { return os << '{' << p.first << " " << p.second << '}'; }
template<class T, class U> std::ostream& operator<<(std::ostream& os, const std::map<T, U>& mp) { os << '{'; for (auto it = mp.begin(); it != mp.end(); ++it) { os << '{' << it->first << ':' << it->second << '}'; if (it != --mp.end()) os << ','; } os << '}'; return os; }
template<class T> std::ostream& operator<<(std::ostream& os, const std::set<T>& st) { os << '{'; for (auto it = st.begin(); it != st.end(); ++it) { os << *it; if (it != --st.end()) os << ','; } os << '}'; return os; }
template<class T> std::istream& operator>>(std::istream& is, std::vector<T>& vec) { size_t n = vec.size(); for (size_t i = 0; i < n; ++i) is >> vec[i]; return is; }

#define all(_) begin(_), end(_)
#define rall(_) rbegin(_), rend(_)

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]: ", debug_out(__VA_ARGS__)
#else
#define debug(...) 1728
#endif

void debug_out() { std::cerr << '\n'; }

template <class Head, class... Tail>
void debug_out(Head&& head, Tail&&... tail) {
  std::cerr << head;
  if (sizeof...(Tail) != 0) std::cerr << ", ";
  debug_out(std::forward<Tail>(tail)...);
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int h, w, d; cin >> h >> w >> d;
  vector<vector<int>> a(h, vector<int>(w));
  cin >> a;

  map<int, pair<int, int>> mp;
  for (int i = 0; i < h; ++i) {
    for (int j = 0; j < w; ++j) {
      mp[a[i][j]] = {i, j};
    }
  }

  vector<int> cost(h * w + 1, 0);

  for (int i = d + 1; i <= h * w; ++i) {
    cost[i] = cost[i - d] + abs(mp[i].first - mp[i - d].first) + abs(mp[i].second - mp[i - d].second);
  }

  int q; cin >> q;
  for (int i = 0; i < q; ++i) {
    int l, r; cin >> l >> r;
    cout << cost[r] - cost[l] << '\n';
  }

  return 0;
}

Measured memory_bytes: 7424
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define inf 1001001001001001001
#define mod 1000000007
#define mod2 998244353a
#define pi acos(-1)
#define all(v) v.begin(),v.end()

bool check(vector<int>a,vector<int>b,int N){
    bool flag=0;
    for(int i=0;i<N;i++){
        if(a.at(i)!=b.at(i)){
            flag=1;
            break;
        }
    }
    return flag;
}
int main(){
    int N;
    cin>>N;
    vector<int>P(N);
    vector<int>Q(N);
    vector<int>R(N);
    int pCount=0;
    int qCount=0;
    int count=0;
    for(int i=0;i<N;i++){
        cin>>P.at(i);
    }
    for(int i=0;i<N;i++){
        cin>>Q.at(i);
    }
    for(int i=0;i<N;i++){
        R.at(i)=i+1;
    }
    do{
        for(int i=0;i<N;i++){
            if(check(P,R,N)==0){
                pCount=count;
            }
            if(check(Q,R,N)==0){
                qCount=count;
            }
        }
        count++;
    }while(next_permutation(R.begin(),R.end()));

    cout<<abs(pCount-qCount)<<endl;
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n; 
  cin >> n;
  vector<int> v(n);
  for (int i=0;i<n;++i) {
    cin >> v[i];
  }
  vector<int> c(n);
  for (int i=0;i<n;++i) {
    cin >> c[i];
  }
  int ans = 0;
  for (int i = 0;i<n;++i) {
    if (v[i]>c[i]) {
      ans += v[i] - c[i];
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <limits>
#include <cfloat>
#include <functional>
using namespace std;

template <class T>
class Edge
{
public:
    int to;
    T cost;
    Edge(){};
    Edge(int to0, T cost0){to = to0; cost = cost0;}
};

template<class T>
void shortestPath(const vector<vector<Edge<T> > >& edges, int start, vector<T>& dist)
{
    const T INF = numeric_limits<T>::max();
    const T EPS = static_cast<T>(1.0e-10);

    dist.assign(edges.size(), INF);
    dist[start] = 0;
    priority_queue<pair<T,int>, vector<pair<T,int> >, greater<pair<T,int> > > q;
    q.push(make_pair(0, start));

    while(!q.empty()){
        pair<T, int> p = q.top();
        q.pop();
        int v = p.second;
        if(dist[v] < p.first - EPS)
            continue;
        for(unsigned i=0; i<edges[v].size(); ++i){
            Edge<T> e = edges[v][i];
            if(dist[v] + e.cost < dist[e.to] - EPS){
                dist[e.to] = dist[v] + e.cost;
                q.push(make_pair(dist[e.to], e.to));
            }
        }
    }
}

const long long X = 100000;

int main()
{
    int n, transferTime;
    string start, goal;
    cin >> n >> transferTime >> start >> goal;

    vector<int> a(n);
    vector<vector<string> > s(n);
    vector<vector<int> > t(n);
    map<string, int> index;

    for(int i=0; i<n; ++i){
        cin >> a[i];
        s[i].resize(a[i]);
        for(int j=0; j<a[i]; ++j){
            cin >> s[i][j];
            index[s[i][j]];
        }

        t[i].resize(a[i]-1);
        for(int j=0; j<a[i]-1; ++j)
            cin >> t[i][j];
    }

    int m = 0;
    for(map<string, int>::iterator it=index.begin(); it!=index.end(); ++it){
        it->second = m;
        ++ m;
    }

    vector<vector<Edge<long long> > > edges(m + accumulate(a.begin(), a.end(), 0));
    int p = m;
    for(int i=0; i<n; ++i){
        for(int j=0; j<a[i]; ++j){
            edges[p+j].push_back(Edge<long long>(index[s[i][j]], transferTime * X + 1));
            edges[index[s[i][j]]].push_back(Edge<long long>(p+j, 0));
        }
        for(int j=0; j<a[i]-1; ++j){
            edges[p+j].push_back(Edge<long long>(p+j+1, t[i][j] * X));
            edges[p+j+1].push_back(Edge<long long>(p+j, t[i][j] * X));
        }
        p += a[i];
    }

    vector<long long> dist;
    shortestPath(edges, index[start], dist);
    long long ret = dist[index[goal]];
    
    if(ret == LLONG_MAX){
        cout << -1 << endl;
    }else{
        ret -= (transferTime * X + 1);
        cout << (ret / X) << ' ' << (ret % X) << endl;
    }

    return 0;
}

Measured memory_bytes: 29360
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;

class Prog
{
    public Prog() { }
    public static int Main()
    {
        new Prog().calc();
        return 0;
    }

    Scanner cin;

    public void calc()
    {
        cin = new Scanner();
        int sx = cin.nextInt();
        int sy = cin.nextInt();
        int tx = cin.nextInt();
        int ty = cin.nextInt();

        int dx = tx - sx;
        int dy = ty - sy;

        for (int i = 0; i < dx; i++) Console.Write("R");
        for (int i = 0; i < dy; i++) Console.Write("U");

        for (int i = 0; i < dx; i++) Console.Write("L");
        for (int i = 0; i < dy; i++) Console.Write("D");

        Console.Write("D");
        for (int i = 0; i < dx + 1; i++) Console.Write("R");
        for (int i = 0; i < dy + 1; i++) Console.Write("U");
        Console.Write("L");

        Console.Write("U");
        for (int i = 0; i < dx + 1; i++) Console.Write("L");
        for (int i = 0; i < dy + 1; i++) Console.Write("D");
        Console.Write("R");

        Console.WriteLine();
    }
}


class Scanner
{
    string[] s;
    int i;

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

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

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

    public int nextInt()
    {
        return int.Parse(next());
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

    public double nextDouble()
    {
        return double.Parse(next());
    }

}

Measured memory_bytes: 2648
#include "bits/stdc++.h"
using namespace std;
#define long int64_t

int main() {
	ios_base::sync_with_stdio( false );

	int N;
	cin >> N;

	vector<string> s( N );
	for( int i = 0; i < N; ++i ) {
		cin >> s[i];
	}

	int ab = 0;
	int a = 0;
	int b = 0;
	int ba = 0;
	for( int i = 0; i < N; ++i ) {
		for( int j = 1; j < s[i].size(); ++j ) {
			if( s[i][j-1] == 'A' && s[i][j] == 'B' ) { ab += 1; }
		}

		if( s[i].front() == 'B' && s[i].back() == 'A' ) {
			ba += 1;
		}
		else if( s[i].front() == 'B' ) {
			b += 1;
		}
		else if( s[i].back() == 'A' ) {
			a += 1;
		}
	}

	if( ba == 0 ) {
		cout << ab + min( a, b ) << endl;
	}
	else if( a == 0 && b == 0 ) {
		cout << ab + ba - 1 << endl;
	}
	else {
		cout << ab + ba + min( a, b ) << endl;
	}

	return 0;
}


Measured memory_bytes: 768
#include<bits/stdc++.h>
#define ll long long
#define MAXN 55

#define INF 0x3f3f3f3f
#define ld long double
using namespace std;
ll mod=1000000007;
ll g[100005]={0};

ll pmod(ll a, ll b, ll N)
{
	ll result = 1;
	// 在求幂之前，我们可以先把 a 限制在模 N 范围内，即把 a 变小
	a = a % N;
	while (b > 0)
	{
		// 如果 b 是奇数，将多出来的一次单独计算并带入结果
		if (b % 2 == 1)
		{
			result = result * a;
			result = result % N;
			b--;
		}
		// b 减小为原来的二分之一
		b /= 2;
		a = (a * a) % N;
	}
	return result;
}

int main(){
    ios::sync_with_stdio(false);
    #define int ll
    int n,k;
    cin>>k>>n;
    int ans=0;
    for(int i=n;i>=1;i--){
        int num=n/i;

        g[i]=pmod(num,k,mod)%mod;
        for(int j=i*2;j<=n;j+=i){
            g[i]=(g[i]+mod-g[j])%mod;
        }

        ans=(ans+g[i]*i%mod)%mod;

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


Measured memory_bytes: 4404