Submission #81664
Source Code Expand
import bisect all_, N, M = map(int, raw_input().split()) L = [int(raw_input()) for i in xrange(N)] xy = [map(int, raw_input().split()) for i in xrange(M)] diff = [] for i in xrange(len(L) - 1): diff.append(L[i + 1] - L[i]) diff.sort() accumulated = [0] sum_ = 0 for i in xrange(len(diff)): sum_ += diff[i] accumulated.append(sum_) for x, y in xy: i = bisect.bisect(diff, x + y) lines = accumulated[i] + (len(diff) - i) * (x + y + 1) lines += min(L[0] - 1, x) lines += min(all_ - L[-1], y) print lines + 1
Submission Info
Submission Time | |
---|---|
Task | D - grepマスター |
User | sekiye |
Language | Python (2.7.3) |
Score | 100 |
Code Size | 564 Byte |
Status | AC |
Exec Time | 1157 ms |
Memory | 26676 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 100 / 100 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 00_sample_01.txt, 00_sample_02.txt, 01_min.txt, 02_rand_00.txt, 02_rand_01.txt, 02_rand_02.txt, 03_randp_00.txt, 03_randp_01.txt, 03_randp_02.txt, 04_maxrandp_00.txt, 04_maxrandp_01.txt, 04_maxrandp_02.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_01.txt | AC | 52 ms | 3272 KB |
00_sample_02.txt | AC | 46 ms | 3224 KB |
01_min.txt | AC | 46 ms | 3272 KB |
02_rand_00.txt | AC | 659 ms | 17552 KB |
02_rand_01.txt | AC | 873 ms | 21796 KB |
02_rand_02.txt | AC | 252 ms | 8344 KB |
03_randp_00.txt | AC | 626 ms | 16432 KB |
03_randp_01.txt | AC | 982 ms | 22836 KB |
03_randp_02.txt | AC | 991 ms | 22960 KB |
04_maxrandp_00.txt | AC | 1140 ms | 26676 KB |
04_maxrandp_01.txt | AC | 1157 ms | 26668 KB |
04_maxrandp_02.txt | AC | 1147 ms | 26668 KB |